[프로그래머스] 스킬트리 / C++ 풀이

문제 링크

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

프로그래머스

 

코드

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

bool isMatchedFromFront(string skill, string order) {
    for(int i = 0; i < order.length(); ++i) {
        if(skill[i] != order[i]) {
            return false;
        }
    }
    
    return true;
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    bool isOrderedSkill['Z' - 'A' + 1] = {false,};
    
    for(const auto& c : skill) {
        isOrderedSkill[c - 'A'] = true;
    }
    
    
    for(const auto& st : skill_trees) {
        string order = "";
        for(const auto& c : st) {
            if(isOrderedSkill[c - 'A'])  {
                order += c;
            }
        }
        
        if(order.length() == 0 || isMatchedFromFront(skill, order)) {
            answer++;
        }
    }
    
    
    return answer;
}

 

접근법

선행 스킬이 필요한 스킬들만 뽑아낸 다음에 이 스킬들이 주어진 선행 스킬 순서를 지키고 있는지 확인한다. isOrderedSkill 배열을 미리 만들어두어 어떤 스킬이 선행 스킬이 필요한 것인지 빠르게 확인할 수 있게 한다.

 

위 코드에서 order문자열은  skill_trees의 요소 중 선행 스킬이 필요한 스킬들만 모인 문자열이다. 이 문자열이 선행스킬을 배우는 순서를 지키고 있는지는 isMatchedFromFront()가 검사한다.