[프로그래머스/Level 2] 스킬트리 (C++)

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

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

 

풀이

문자나 문자열을 가지고 순서를 비교해야 한다면 map 자료구조를 이용하는 것을 반드시 생각해보자

 

전체 코드

#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> um;
    
    // 선행 스킬 등록 : (C, 1), (B, 2), (D, 3)
    for(int i = 0; i < skill.size(); i++) {
        um[skill[i]] = i + 1;
    }
    
    for(string s : skill_trees) {
        int count = 1;
        bool flag = true;
        for(char ch : s) {
            // 스킬 순서가 맞지 않으므로 종료
            if(um[ch] > count) {
                flag = false;
                break;
                
            // 스킬 순서가 맞으면 다음 스킬을 배울 수 있도록 count 증가
            } else if(um[ch] == count) {
                count++;
            }
        }
        if(flag) answer++;
    }
    
    return answer;
}