[2023년 11월 22일]스킬트리(16분)

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

구현 아이디어 3분 구현 13분

풀이

check 배열에 선행 스킬이 있는 스킬들을 1 대입하여 나중에 skill_trees[i]를 돌 때 선행 스킬과 관련 없는 스킬은 continue 했다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int check[26];

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    queue<char> Q;
    
    // skill_trees[i]에서 선행 스킬 없이 배울 수 있는 스킬은 넘어가자.
    for(int i = 0; i < skill.length(); ++i)
    {
        check[skill[i] - 'A'] = 1;
        Q.push(skill[i]);
    }
    
    for(int i = 0; i < skill_trees.size(); ++i)
    {
        bool learn = true;
        string skill_tree = skill_trees[i];
        
        for(int j = 0; j < skill_tree.length(); ++j)
        {
            if(check[skill_tree[j] - 'A'] == 0) continue;
            else
            {
                if(skill_tree[j] == Q.front())
                    Q.pop();
                else
                {
                    learn = false;
                    break;
                }
            }
        }
        
        while(!Q.empty()) Q.pop();
        for(int j = 0; j < skill.length(); ++j)
            Q.push(skill[j]);
        
        if(learn) ++answer;
    }
    
    return answer;
}