[Programmers] 스킬트리 - travelbeeee

 

---

[ 알고리즘풀이 ]

 우리는 주어진 skill_trees 중 skill 과 관련된 알파벳만 신경쓰면 되므로, 먼저 skill 을 순회하며 skill 에 나온 Alphabet을 체크한다. 그 후, skill_trees의 tree들을 모두 순회하며, pointer j 를 이용해 tree 중 우리가 신경써야되는 알파벳이 현재 주어진 skill 과 순서가 맞는지 확인하고 아니라면 다음 tree로 넘어간다.

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    bool checkAlphabet[26]={};
    for(int i = 0; i < skill.length(); i++)
        checkAlphabet[skill[i] - 'A'] = 1;
    
    for(int i = 0; i < skill_trees.size(); i++){
        bool check = true;
        int j = 0;
        for(int k = 0; k < skill_trees[i].length(); k++){
            if(!checkAlphabet[skill_trees[i][k] - 'A'])
                continue;
            if(skill[j] != skill_trees[i][k]){
                check = false;
                break;
            }
            j++;
        }
        if(check)
            answer++;
    }
    return answer;
}

---