[프로그래머스] level 2 - 스킬트리 (C++)

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

 

문제 풀이

단순 비교 말고 어떤 방식으로 접근해야할지 꽤 고민했던 문제.

내가 선택한 방법은 정해진 스킬트리의 인덱스를 따라가는 방법이다.

먼저 정해진 스킬트리에서 현재 배워야 할 스킬의 인덱스를 저장한다.

그리고 유저가 만든 스킬트리에 순서대로 방문하여 해당 스킬이 스킬트리에 해당하는 스킬인지 find 연산을 통해 알아낸다.

만약 해당한다면 현재 배워야 할 스킬의 인덱스와 같은지 비교하고, 맞다면 인덱스를 증가시키고 다르다면 순서에 맞지 않은 스킬을 배운 것이므로 break 후 다른 스킬트리로 넘어간다.

만약 스킬트리의 스킬을 모두 배웠거나, 유저의 스킬트리가 먼저 끝났다면 올바른 스킬트리로 간주하여 answer 값을 증가시킨다.

 

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int len = skill.size();

    for (int i = 0; i < skill_trees.size(); i++)
    {
        int idx = 0; // 스킬트리 순서를 나타낼 인덱스
        for (int j = 0; j < skill_trees[i].size(); j++)
        {
            int order = skill.find(skill_trees[i][j]);
            if (order != string::npos)
            {
                if (order != idx) break;
                else idx++;
            }
            
            if (idx == len || j == skill_trees[i].size() - 1)
            {
                answer++;
                break;
            }
        }
    }

    return answer;
}