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

1. 문제 개요

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

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

1-1. 설명

선행 스킬은 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻한다. 예를 들면 선행 스킬 순서가 스파크 -> 라이트닝 볼트 -> 썬더 일 때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 한다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개 변수로 주어질 때, 가능한 스킬 트리의 개수를 return 하는 solution 함수를 작성한다.

1-2. 제한 사항

 - 스킬은 알파벳 대문자로 표기, 모든 문자열은 대문자로만 이루어짐

 - 스킬 순서와 스킬트리는 문자열로 표기

 - 선행 스킬 순서 skill의 길이는 1 이상 26 이하, 스킬은 중복으로 주어지지 않음

 - skill_trees의 길이는 1 이상 20 이하 배열

 - skill_trees의 원소는 스킬을 나타내는 문자열

 - skill_trees의 원소 길이는 2 이상 26 이하 문자열, 스킬은 중복으로 주어지지 않음

---

2. 구현

2-1. 풀이

스킬트리 정보가 담긴 문자열을 하나씩 비교하며, 선행 스킬이 존재하지 않을 때에는 개수를 하나 올려주고 다음 문자열을 탐색한다. 선행 스킬이 존재할 시 선행 스킬만 따로 문자열에 새로 저장하여 선행 스킬과 비교하며 순서가 잘 지켜졌으면 1을 더한다. 

2-2. 코드

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string result_skill;
    
    for (string skill_tree: skill_trees) { // 스킬트리 정보가 담긴 문자열 나열
        result_skill = "";
        for (int i = 0; i < skill_tree.size(); i++){ 
            if (skill.find(skill_tree[i]) != string::npos) {
            // 선행 스킬 순서에 존재하는 문자 찾은 후 저장
                result_skill += skill_tree[i];
            }
        }
        
        if (result_skill == ""){ // 스킬트리에 선행 스킬이 존재하지 않는다면 continue
            answer++;
            continue;
        }
        
        for (int i = 0; i < result_skill.size(); i++) { 
            if (skill[i] != result_skill[i]) break; // 선행스킬의 순서가 동일하지 않다면 break
            else if (i == (result_skill.size() - 1) && skill[i] == result_skill[i]){
            // 선행스킬 순서가 동일하면 1을 더함
                answer++;
            } 
        }
    }
    return answer;
}