프로그래머스 - 스킬트리 [C++]

 이 문제는 맵을 이용해서 풀었다. 일단 입력이 매우 작으므로 단순 구현으로도 시간 초과가 나지 않는다. 시간 단축을 위해 map에서 skill에 나오는 알파벳을 true로 설정했다. skill_trees에 대해 반복문을 돌리면서, 해당 문자열 루프 안에서 mp[s]가 true일 때 skill에 알맞은 순서이면 index++을, 맞지 않으면 break를 통해 다음 문자열을 본다. 문제에 주어진 대로 구현하면 풀리는 문제이다.

 

 

 

 

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for (string& st : skill_trees) {
        int index = 0;
        map<char, bool> mp;
        
        // init
        for (char s : skill) {
            mp[s] = true;
        }
        
        bool flag = true;
        for (char s : st) {
            if (mp[s]) {
                if (skill[index] == s) {
                    index++;
                }
                else {
                    flag = false;
                    break;
                }
            }
        }
        
        if (flag) {
            answer++;
        }
    }
    
    return answer;
}