프로그래머스 / summer/winter coding(~2018) / 스킬트리

 

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

프로그래머스

 

 

#include <map>
#include <vector>
#include <string>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, int> myTree;
    //myTree의 key에 skill[i]의 char을, value에 인덱스+1을 저장한다.
    for (int i = 0; i < skill.length(); i++) myTree[skill[i]] = i + 1;
    //skill_trees를 검색한다.
    for (auto search : skill_trees)
    {
        //index 는 선행 스킬의 인덱스이며, 초기값은 1이다.
        //스킬을 배울 수 있는지 판별하는 bool 변수를 true 로 준다.
        int index = 1;
        bool learn = true;
        //search의 길이만큼 검색한다.
        for (int i = 0; i < search.length(); i++)
        {
            //search[i]번째의 키값의 value가 index보다 클 경우
            if (myTree[search[i]] > index)
            {
                //선행 스킬을 배우지 않았으므로 스킬을 배울 수 없다.
                learn = false;
                break;
            }
            //search[i]번째의 키값의 value가 index와 같을 경우
            else if (myTree[search[i]] == index)
            {
                //배워야 하는 선행 스킬과 인덱스가 같으면 배울 수 있다.
                //이제 방금 배운 스킬의 다음 인덱스가 선행 스킬이 되므로
                //index를 ++ 시켜준다.
                index++;
                //계속 검색한다.
                continue;
            }
        }
        //learn이 false로 빠지지 않고 무사히 빠져나왔을 경우 스킬을 배울 수 있으므로
        //answer값을 ++ 해준다.
        if (learn == true)answer++;
    }
    return answer;
}