[Programmers] 스킬트리

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

문제 요약

스킬이 주어져 있습니다. 이 스킬 순서대로 스킬들이 정렬되어있어야 하고, 제대로 정렬되어 있는 스킬들이 스킬트리내에 몇 개인지 구하는 문제입니당 예를들어 ABCD라는 스킬이 있고, ACBDEFS라고 스킬트리 내에 하나가 주어지면 ABCD순서대로 정렬되어 있지 않기 떄문에 count해서는 안되고, ABCEDFS일 경우는 순서대로 정렬되어 있기 때문에 성립되어 count해주면 됩니다.

문제 풀이

생각나는 그대로 구현해보면 됩니다. 먼저 검사해야할 스킬들이 담긴 스킬트리는 배열로 주어집니다. 배열을 0부터 하나씩 스킬과 비교해보면서 조건에 성립하는지 확인해보면 됩니다. 조건에 성립하는 지 확인하는 방법은 아래와 같습니다. 스킬트리 내의 비교하는 스킬을 A라고 부르겠습니다.

1. 스킬의 첫번째 값과 A의 첫번째 값을 비교한다.

2. 만약 같다면 스킬의 첫번째 값을 지워준다.

2. 다르다면 스킬의 첫번째 값부터 마지막 값까지 반복문을 들려 A의 첫번째 값과 비교하여 같은 값이 있을 경우 break문을 걸고 빠져나온 후, 조건이 성립되지 않은 경우이므로 A의 값들과의 비교에서도 break해준다. 없을 경우 그대로 빠져나오고 A의 index 값을 하나 올려 1,2번 과정을 반복한다. 

여기서 flag 변수를 통해 조건이 성립 유무를 판단해줍니다. 코드는 아래와 같습니다.

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    string skill_copy = skill; 
    for (int i = 0; i < skill_trees.size(); i++) {
        string temp = skill_trees[i];
        skill = skill_copy;
        bool flag = false;
        for (int j = 0; j < temp.size(); j++) {
            if (temp[j] == skill[0]) {
                skill.erase(skill.begin());
            } else {
                for (int k = 1; k < skill.size(); k++) {
                    if (temp[j] == skill[k]) {
                        flag = true;
                        break;
                    }
                }
            }
            if (flag) {
                break;
            }
        }
        if (!flag) {
            answer++;
        }
    }
    return answer;
}

 

잠시 학교 중간고사와 과제 폭탄을 맞아.... 알고리즘 문제 풀이에 소홀했더니 쉬워 보이는 문제를 골라 풀어도 풀리지 않더라구요... 꾸준히 하는게 중요한 것 같습니당 일주일에 세문제씩은 꼬박꼬박 풀어야겠습니다! ㅎ.ㅎ

모두 화이팅~.~