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

programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

 

처음에 큐 자료구조를 이용해서 문제를 풀었습니다.

skill 에 있는 순서대로 스킬을 배울 수 있기때문에

"순서대로" 라는 마인드로 큐를 사용했는데..

 

3중 for문이 나오면서 풀이가 점점 나락으로 빠졌습니다.

 

그래서 대안을 찾은게 해쉬인데

key에 배울 수 있는 스킬, value 에 그 스킬의 순서(입출력 예에서 1번째로 배우는 C의 경우 1번을 부여) 를 부여했습니다.

 

현재의 power(배울 수 있는 스킬의 value 값) 을 가지고

스킬을 배울 수 있으면 power++ 해서 다음 스킬도 배울 수 있게 값을 올려주고

 

혹시 배울 수 없는 스킬이 나올경우 break 해서 반복문을 빠져나왔습니다.

 

반복문을 빠져나온 후 모든 스킬트리를 다 배울 수 있었던 경우를 bool형으로 정의해 

가능하면 answer++ 해주었습니다.

 

 

이번에 공부하며 알게 된 사실인데  해쉬의 key값을 따로 지정해주지 않을 경우

그 key를 탐색할시 value 값은 0이 나온다는 구조를 알게되었습니다.

유용하게 쓸 수 있을 것 같습니다.

 

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    unordered_map<char, int> map;
 
    //skill 에 있는 스킬(알파벳)을 순서대로 넣고 value 값을 올려줌
    for (int i = 0; i < skill.size(); i++)
        map[skill[i]] = i + 1;
 
    for (auto sktree : skill_trees) {
 
        int power = 1;
        bool right = true;
        for (int i = 0; i < sktree.size(); i++) {
            //만약 map에 있는 벨류값이 power보다 높다면 스킬트리 오류
            if (map[sktree[i]] > power) {
                right = false;
                break;
            }
            //map에 있는 벨류값과 현재 power가 같다면 배울 수 있는 스킬
            //배운 후 power을 올려줌
            else if(map[sktree[i]] == power)
                power++;
        }
        if (right == true)
            answer++;
    }
    return answer;
}