[프로그래머스] 스킬트리 (배열)

이 글에서는 프로그래머스 - 스킬트리 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

처음에는 입출력 예시를 잘못봐서 아예 코드를 잘못 짰었습니다.

무조건 스킬을 다 써야 하는 줄 알았는데 순서만 맞으면 되지, 순서가 명시되어 있는 모든 스킬들을 쓰지 않아도 된다는 것을

틀리고 나서 알았습니다. 그래서 다시 짜고 말았다는...ㅎ

이 문제야 말로 사람마다 푸는 방식이 다 다를 것 같은데 저는 아래와 같이 풀었고 해당 그림은 문제에 예시를 사용했습니다.

참고로, 아래 풀이는 스킬이 중복되지 않기 때문에 가능한 풀이 입니다.

풀이 1

그림이 글보다 설명하기 쉬울거라고 생각했던 지난 과거를 반성하게 됩니다. 아래 [그림 1]은 과연 제가 제대로 잘 표현한 것일까요..?

문제의 핵심은 간단합니다.

1. 알파벳은 26개이므로 size = 26이고 -1로 초기화 된 배열 사용

2. skill에 나와있는 순서대로 배열 값 변경 (C - Z - A라면 arr[2] = 0, arr[25] = 1, arr[0] = 3)

3. skill_trees에 있는 스킬트리들의 순서가 arr에 있는 값 순서와 같은지 비교.

 

일단, 코드를 보면서 설명하는 것이 나을 것 같아 코드부터 쓰도록 하겠습니다. 코드를 복사하고 싶으신 분들은 아래 더보기를 클릭하시고 설명을 보고 싶으시다면 [그림 2] 하단에 있는 설명을 보시면 됩니다.

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = skill_trees.size();
    // skill order array
    int arr_skill[26];
    for(int i = 0; i < 26; i++){
        // default : initialize to -1
        arr_skill[i] = -1;
    }
    // if letter is in string 'skill' change value to skill's order
    for(int pos = 0; pos < skill.length(); pos++){
        int letter = skill[pos];
        arr_skill[letter - 65] = pos;
    }
    
    // check skill tree
    for(int i = 0; i < skill_trees.size(); i++){
        // check current skill
        string curr = skill_trees[i];
        // compare string 'curr' with array
        int skillOrder = 0;
        for(int j = 0; j < curr.length(); j++){
            int letter = curr[j];
            if(arr_skill[letter - 65] > -1){
                if(arr_skill[letter - 65] > skillOrder){
                    answer--;
                    break;
                } else{
                    skillOrder++;
                }
            }
        }          
    }  
    return answer;
}

[그림 1]

[그림 2]

#7 : 답은 skill_trees의 크기로 시작합니다. 후에 나오겠지만 skill 순서를 지키지 않은 원소들을 탈락시키면서 하나씩 뺄 예정입니다.

#9 ~ 13 : arr_skill이라는 크기가 26이라 순서대로 알파벳을 지칭할 배열을 만들고 -1로 초기화시킵니다.

#14 ~ 18 : skill에 나온 순서대로 그 순서를 배열 값으로 넣어줍니다. (C - Z - A라면 arr[2] = 0, arr[25] = 1, arr[0] = 3)

#23 : skill_tress 내에 주어진 하나하나의 skill tree들을 확인하므로 현재 확인하고 있는 skill tree 문자열이 curr 입니다.

#25 : skill order는 0부터 시작합니다. 배열에 해당 알파벳 값이 -1이 아닐 때(= skill에 포함된 알파벳임) skill order와 비교를 합니다. 현재 skill order가 0인데 배열에 있는 값이 2라면 순서 위반인 것입니다.

#28 ~ 35  : curr에서 지금 살펴보고 있는 한 글자의 배열 값이 -1이 아니라는 것은 해당 글자가 skill에 포함되어 있다는 뜻입니다.

#29 ~ 34 : curr에서 지금 살펴보고 있는 한 글자가 skill에 포함되어 있는 글자이면서 그 글자의 배열값을 보니 skill order 보다 크다면 순서를 위반 한 것입니다. 그러므로 answer에서 하나를 빼고 다음 skill tree를 확인합니다. 만약 skill order에 맞게 배열 값이 들어가 있으면 다음 비교를 진행해야하므로 skill order를 하나 증가시킵니다.