[프로그래머스] Level 2 스킬트리

문제 링크

programmers.co.kr/learn/courses/30/lessons/49993

풀이

선행 스킬을 이용해 각 스킬을 배워야하는 순서를 배열에 1, 2, 3, ... 순서로 체크한다.
체크되지 않은 나머지 스킬들은 언제 배워도 상관 없으므로 적당히 0으로 둔다.

이제 각 스킬트리를 순회하면서 선행 스킬에 포함되는 스킬의 순서가 1, 2, 3, ... 순서로 증가하는지 확인한다.
이 순서가 지켜지지 않았다는 것은 불가능한 스킬트리라는 뜻이 된다.

C++ 코드

#include <bits/stdc++.h>
using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int order[26]{};
    for (int i = 0; i < skill.size(); ++i) order[skill[i] - 65] = i + 1;
    
    int ans = 0;
    for (string& it : skill_trees) {
        bool f = 1;
        for (int p = 0, i = 0; i < it.size(); ++i) {
            int tmp = order[it[i] - 65];
            if (tmp == 0) continue;
            if (p + 1 != tmp) f = 0;
            p = tmp;
        }
        ans += f;
    }
    
    return ans;
}