C++ / 프로그래머스 / 스킬트리

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

 

문제풀이

 

스킬은 항상 대문자만 주어진다. 스킬은 순서대로 배워야 하므로 벡터를 선언하여 스킬의 이름과 순서를 입력한다.

예제를 보면 skill = "CBD"이다. 이때, "BACDE"는 안 되는 이유가 C를 배워야 B를 배울 수 있기 때문이다.

따라서 현재 배우고 있는 스킬의 위치를 나타내기 위한 인덱스인 s_idx 변수를 두고,

스킬트리에 순서대로 배워야 하는 스킬이 나오면 s_idx와 같은지를 판단하면 된다.

 

선행 스킬과 관련없는 스킬일 경우 continue를 통해 다음으로 넘어간다.

만약 선행 스킬이 나왔을때 s_idx와 같다면 순서대로 배운 것이므로 ++s_idx를 하고 다음으로 넘어간다.

만약 선행 스킬이 나왔을때 s_idx와 다르다면 순서대로 배운 것이 아니므로 break를 하여 반복문을 종료한다.

flag가 true라면 제대로 배운 것이므로 ++answer, 반대라면 아무 행동도 하지 않는다.

 

이런 식으로 모든 스킬트리를 탐색하면 된다.

 

코드

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer(0);

    vector<int>alp(26, -1);

    for (int idx = 0; idx < skill.size(); ++idx) {
        alp[skill[idx] - 'A'] = idx;
    }

    for (int idx = 0; idx < skill_trees.size(); ++idx) {
        int s_idx(0);
        bool flag(true);
        for (int s_cnt = 0; s_cnt < skill_trees[idx].size(); ++s_cnt) {
            char c = skill_trees[idx][s_cnt] - 'A';
            if (alp[c] == -1) continue;
            else if (alp[c] == s_idx)  ++s_idx;
            else if (alp[c] != s_idx) {
                flag = false;
                break;
            }
        }
        if (flag == true) ++answer;
    }

    return answer;
}