[Algorithm] Programmers :: 스킬트리

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

프로그래머스

int solution(string skill, vector<string> skill_trees) 
{
    int answer = 0;
 
    map<char, char> m;
    m[skill[0]] = '?'; // 
    
    for (int i = 1; i < skill.size(); ++i)
    {
        m[skill[i]] = skill[i - 1];
    }
 
    for (int i = 0; i < skill_trees.size(); ++i)
    {
        string curSkill = skill_trees[i];
        char prevSkill = '?';
        bool isCheck = true;
 
        for (int j = 0; j < curSkill.size(); ++j)
        {
            if (m.count(curSkill[j]) == 0) continue;// 무관한 스킬이면
 
            if (m[curSkill[j]] != prevSkill) // 올바른 관계가 아니면
            {
                isCheck = false;
                break;
            }
 
            prevSkill = curSkill[j];
        }
 
        if (isCheck) ++answer;
    }
 
    return answer;
}

종속관계의 스킬들은 먼저 각자의 부모를 지정한다. 맨 처음스킬같은 경우는 임의로 '?'을 부모로 지정한다.

그리고 prevSkill변수로 현재 어디까지 종속관계의 스킬트리가 진행됐는지를 체크한다. 물론 초깃값은 '?'이다.

 

이후 스킬트리를 검사하면서 종속관계랑 상관없는 스킬은 그냥 넘기고(map의 count를 이용해 종속관계의 스킬인지 아닌지를 판별), 종속관계의 스킬일 경우 해당 스킬의 부모값과 prevSkill값이 일치한지 체크하고 여부에 따라 적절한지 아닌지 판단한다.