스킬트리 (프로그래머스)

스킬 트리가 스킬 순서의 조건을 지키는지를 검사하는 문제였다.

 

스킬 순서가 CBD인 경우 스킬 트리에서 B 스킬을 찍기 위해서는 C가 먼저 나와야 한다. CBD는 순서만 지키면 되지 스킬 트리에서 해당 스킬들이 안 나와도 상관없다.

 

처음부터 검사를 하는 경우 어떻게 접근해야 하는지 살펴보자.

우선 첫 번째 스킬 나올때 까지 스킬 트리의 스킬들을 차례대로 검사한다. 만약 해당 스킬이 나왔다면 두 번째 스킬로 넘어가 나올 때까지 검사하면 된다. 스킬 트리에서 스킬이 안 나오더라도 상관없으므로 올바른 스킬 트리이다.

하지만, 해당 스킬 이후 번째 스킬이 스킬 트리에서 먼저 나온다면, 그것은 불가능한 스킬 트리이다.

 

코드는 다음과 같다.

#include <string>
#include <algorithm>
using namespace std;

int solution(string skill, vector<string> skill_trees) 
{
    int answer = 0;
    // 스킬트리들을 검사한다.
    for(const auto s_tree : skill_trees)
    {
        // 스킬의 첫번째 부터 검사한다.
        auto iter = skill.begin();
        // 일단 증가시키고 불가능하면 감소시킨다.
        ++answer;
        for(const auto s : s_tree)
        {
            // 스킬트리에서 해당 번째 스킬 이후 스킬이 먼저 나온다면
            if(skill.end() != find(iter + 1, skill.end(), s)) 
            {
               // 그것은 불가능한 스킬이다.
                --answer;
                break;
            }
            // 스킬을 모두 검사했다면 올바른 순서의 스킬트리가 나왔다는 뜻으로
            // 검사를 생략한다.
            if(iter == skill.end()) break;
            // 해당 번째 스킬과 같은 스킬을 스킬트리에서 찾았다면
            // 검사를 위한 다음 번째 스킬로 넘어간다.
            if(s == *iter) ++iter;
        }
    }
    return answer;
}