스킬트리(20분)

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

구현 아이디어 5분 구현 15분

풀이

1. 선행 스킬 정보가 있는 문자열을 처음부터 순회해 하나씩 queue1 컨테이너에 담아준다.
2. 더불어 char check[26]의 배열을 만들어 선행 스킬과 관련이 있는 인덱스는 다른 스킬과 구분될 수 있도록 1을 넣는다.
3. 사용자가 입력한 스킬트리를 순회하면서 선행 스킬과 관련 있는 문자열은 queue2에 넣고 선행 스킬과 관련 없는 문자열은 queue2에 넣지 않는다.
4. 선행 스킬 정보가 담긴 queue1 컨테이너와 사용자가 입력한 스킬 중에 선행 스킬과 관련이 있는 스킬만 넣은 queue2 컨테이너가 만들어졌다.
5. 이제 이 둘을 비교하며 같지 않다면 answer을 올리지 않는다. 스킬을 모두 배울 수 있다면 queue2가 empty가 된다. 그럴 경우 answer을 올려준다.

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

using namespace std;

int ch[26];

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    // 원본, 사용자가 입력한 스킬트리 중 선행 스킬과 연관되어 있는 스킬의 큐
    queue<char> q1, q2;
    
    for(int i = 0; i < skill.size(); ++i)
    {
        q1.push(skill[i]);
        ch[skill[i] - 'A'] = 1;
    }
    
    for(int i = 0; i < skill_trees.size(); ++i)
    {
        int j = 0;
        for(j = 0; j < skill_trees[i].size(); ++j)
        {
            char c = skill_trees[i][j];
            if(ch[c - 'A']) q2.push(c);
        }
        
        bool can = true;
        queue<char> cp(q1);
        
        while(true && !q2.empty())
        {
            char cq1 = cp.front();
            char cq2 = q2.front();
            
            if(cq1 != cq2)
            {
                can = false;
                break;
            }
            else
            {
                cp.pop();
                q2.pop();
            }
            
            if(q2.empty())  break;
        }
        
        if(can) answer++;
        while(!q2.empty()) q2.pop();
    }
    
    return answer;
}

---

개인적인 감상.
사람들의 풀이와 비교하면 내 풀이는 길이가 너무 길다! 정확하지만 깔끔하게 풀고 싶다. 공부 많이 하자.

---

다른 분의 깔끔한 풀이를 공부하여 다시 풀었다.

#include <string>
#include <vector>

using namespace std;

bool skill_tree_check(const string& skill_tree, const string& skill)
{
    bool broken = false;
    int prev = 0;
    
    for(auto s : skill)
    {
        int idx = skill_tree.find(s);
        
        // 찾았다.
        if(idx != string::npos)
        {
            if(broken || idx < prev) return false;
            else prev = idx;
        }
        // 못 찾았으면 실상 스킬 트리의 순서는 지킬 수 없게 된 것.
        // 이제 사용자의 skill_tree에서 선행 스킬이 필요한 스킬이 없기를 바라야 함.
        else broken = true;
    }
    
    return true;
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for(int i = 0; i < skill_trees.size(); ++i)
    {
        if(skill_tree_check(skill_trees[i], skill)) ++answer;
    }
    
    return answer;
}