Programmers : 스킬트리

풀이요약

맵

풀이상세

1. map을 통해, 각 문자를 키로, 문자의 인덱스를 값으로 받는다.

2. 각 스킬트리마다 -1을 시작으로, 만약 현재 문자가 map에 존재하는 경우, 해당 키의 값과 idx+1 이 서로 일치하는지 확인한다.

3. idx+1 과 동일하면 idx를 idx+1로 바꾸고, 아닌 경우는 순서가 맞지 않으니 리턴한다.

배운점

• 정답률과 문제의 난이도는 언제나 비례하는 건 아니다.

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<char,int> m;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    for(int i=0; i<skill.size(); i++) {
        m[skill[i]]=i;
    }
    for(int i=0; i<skill_trees.size(); i++) {
        int idx = -1;
        bool check = true;
        for(int j=0; j<skill_trees[i].size(); j++) {
            if(m.find(skill_trees[i][j])!=m.end()) {
                if(m[skill_trees[i][j]] == idx+1) {
                    idx = idx+1;
                } else {
                    check = false;
                    break;
                }
            }
        }
        if(check) answer++;
    }
    return answer;
}