[Lv 2] 스킬트리

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

프로그래머스

 

이 문제는 map을 활용해서 해결할 수 있다.

 

문제에서 skill 문자열에 순서가 있는 스킬이 주어진다.

따라서 map에 순서가 있는 문자를 저장해둔다.

 

스킬트리 배열을 순회하고 현재 배울 스킬이 순서가 있는 스킬이고, 순서가 맞다면

배울 순서 인덱스를 증가시켜 다음 스킬이 배울 수 있는 스킬인지 결정한다.

 

만약 순서가 없는 스킬일이거나 순서가 맞지 않는 경우

순서가 맞지 않는지 확인하기 위해 map에 문자를 검색한다.

순서가 맞지 않다면 반복을 멈춘다.

 

#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, bool> skill_map;
    for(int i = 0;i<skill.length();i++)
        skill_map[skill[i]] = true;
    
    for(int i = 0;i<skill_trees.size();i++){
        string skill_tree = skill_trees[i];
        int skillIdx = 0;
        bool isClear = true;
        for(int j = 0;j<skill_tree.length();j++){
            if(skill[skillIdx] == skill_tree[j]){
                skillIdx++;
            }
            else{
                if(skill_map[skill_tree[j]]){
                    isClear = false;
                    break;
                }
            }
        }
        if(isClear)
            answer++;
    }
    return answer;
}