[Summer/Winter coding -2018] 스킬트리

스킬트리

코딩테스트 연습 - 스킬트리

 

문제 설명

정해진 스킬 순서를 올바르게 배웠는지 체크하는 문제.

스킬을 의미하는 알파벳 사용 여부와 skill의 순서로 skill_trees들을 체크한다.

문제 풀이

소스코드 : C++

1. skill에 있는 스킬들을 true표시 해둔다.
2. skill_trees에 담긴 스킬들을 탐색한다.
3. 해당 스킬이 skill에 포함 된 문자라라면 순서가 맞는지 체크한다.
4. 순서를 의미하는 index, skill[index] == s[j]이면 다음 스킬을 체크한다.
5. 그렇지 않으면 순서가 맞지 않으므로 break
6. 위과정을 반복하여 스킬의 모든 길이를 탐색했으면 예외가 없으므로 answer++해준다.
7. 위 과정을 반복한다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    vector<bool> check(26);    

    for (int i = 0; i < skill.length(); i++)    
        check[skill[i] - 65] = true;

    for (int i = 0; i < skill_trees.size(); i++) {
        int index = 0;
        int j;
        string s = skill_trees[i];
        for (j = 0; j < s.length(); j++) {
            if (check[s[j] - 65]) {
                if (skill[index] == s[j]) index++;
                else break;
            }
        }
        if (j == skill_trees[i].length())
            answer++;
    }
    return answer;
}

소스코드 : Python

좀 쉬운방법이 없을까 하다가 다른 풀이를 참고했다. 덕분에 for else문을 알게되었다.

c++ 코드에서 23번째 줄

if (j == skill_trees[i].length())
    answer++;

이 코드와 같다고 보면된다.

1. 탐색해야할 skills의 원소가 skill안에 있으면 배워야할 순서인 skill_list의 맨 앞의 원소와 비교한다.
2. 비교한 두 문자가 만약 다르면 break를 걸어준다.
3. 같으면 끝까지 탐색한다.
4. 끝까지 탐색했다면 answer +=1을 해준다.

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer