Level 2. 스킬트리

Level 2. 스킬트리

 

 

선행 스킬 정보를 앞에서부터 순서대로 1, 2, 3, ...으로 map에 배정한다.

• unordered_map은 마지막 원소를 가져오는 방법이 없어 map을 사용했다.

 

선행 스킬 중 마지막 스킬을 last에 저장한다.

 

현재 스킬이 선행 스킬이고, 마지막 선행 스킬이 현재 스킬의 직전 스킬이면 마지막 선행 스킬을 갱신한다.

• 현재 선행 스킬이 선행 스킬 정보의 마지막 스킬이면, 뒤는 더 확인할 필요가 없으므로 종료한다.

현재 스킬이 선행 스킬인데, 마지막 선행 스킬이 현재 스킬의 직전 스킬이면 아니면 스킬 트리를 어긴 것이다.

 

#include <iostream>
#include <vector>
#include <map>
#include <numeric>

using namespace std;

int solution(string skill, vector<string> skill_trees)
{
    int answer = 0;
    map<char, int> mp;

    for (int i = 0; i < skill.length(); ++i)
        mp[skill[i]] = i + 1;

    for (string& sk_tree : skill_trees)
    {
        char last = '\0';
        bool bSuccess = true;

        for (char c : sk_tree)
        {
            if (mp[c] - 1 == mp[last])
            {
                if (c == mp.rbegin()->first)
                    break;
                else
                    last = c;
            }
            else if (mp[c])
            {
                bSuccess = false;
                break;
            }
        }

        if (bSuccess)
            ++answer;
    }

    return answer;
}