[프로그래머스] 스킬트리 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

map에 해당 스킬과 해당 스킬을 배우기 위해 필요한 스킬들의 개수를 담을 것입니다.

이렇게 담아놓으면 나중에 스킬 트리를 앞에서부터 읽으면서 해당 스킬을 배울 때 필요한 스킬 개수가 0이라면

바로 배우면 되는 것입니다.

하지만! 해당 스킬을 배울 때 필요한 개수가 0이 아니라면

선행 스킬을 다 배우지 않은 것인데 배울 수 없는 스킬임을 판별할 수 있습니다.

 

이때 현재까지 배워둔 스킬의 개수를 cnt 변수로 관리하면 편리합니다.

 

전체 코드

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

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0; // 가능한 개수(-1 => 0)
    map<char,int> m; // <스킬, 이스킬을 배우기위한 선행 스킬의 개수>
    
    for(int i=0; i<skill.length(); i++) {
        m.insert({skill[i], i}); // 스킬을 배우기위해 앞서 배워야하는 스킬 개수
    }
    
    for(int i=0; i<skill_trees.size(); i++) {
        bool able = true; // 이 스킬트리가 가능한가?
        int cnt = 0; // 현재까지 몇개의 스킬을 배웠는가?

        // 스킬트리 탐색
        for(int j=0; j<skill_trees[i].length(); j++) {
            if(m.find(skill_trees[i][j]) != m.end()) { // skill에 존재하는 문자라면
                if(m[skill_trees[i][j]] != cnt) { // 내가 앞서 배운 스킬들의 개수와 일치하는가?
                    able = false; // 일치하지 않으면 선행스킬이 올바르지 않은것임.
                    break;
                } else { // 앞서 배워야할 개수와 일치하면 해당 스킬 획득
                    cnt++;
                }
            }
        }
        
        if(able) { // 이 스킬트리가 가능한가?
            answer++;
        }
    }
    
    return answer;
}