프로그래머스 - 스킬트리

문제

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

프로그래머스

선행 스킬 조건을 만족한 스킬 트리의 개수를 구하는 문제였다.

 

문제 풀이

해시맵에 스킬과 선행 스킬을 키밸류로 저장하고 isLearn 배열을 이용해 선행 스킬이 있는 스킬인 경우 선행 스킬을 배웠는지 확인하도록 했다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<char,char> skillMap; //스킬, 선행스킬

int isAvailableSkillTree(string skillTree){
    int isLearn[26]; //A~Z 배움 여부
    fill(&isLearn[0], &isLearn[25], 0);
    
    for(int i=0;i<skillTree.size();i++){
        char nowSkill = skillTree[i];
        //printf("nowSkill: %c\n",nowSkill);
        if(skillMap.count(nowSkill) == 1){ //선행스킬 존재
            //printf("선행스킬: %c 배움여부: %d\n", skillMap[nowSkill], isLearn[skillMap[nowSkill]-'A']);
            
            if(isLearn[skillMap[nowSkill] - 'A'] == 0){
                return 0;
            }            
        }
        isLearn[nowSkill - 'A'] = 1;
    }                                                                
    return 1;
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for(int i=1;i<skill.size();i++){ //맨 처음은 선행스킬 없음
        skillMap.insert({skill[i], skill[i-1]});
    }
    
    for(int i=0;i<skill_trees.size();i++){
        if(isAvailableSkillTree(skill_trees[i]) == 1){
            answer++;
        }
        //printf("\n");
    }
    
    return answer;
}