스킬트리(프로그래머스)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/49993

프로그래머스

 

문자열 비교 문제이다.

 

 

skill 이라는 문자열과 skill_trees 라는 배열이 입력으로 주어질 때

( ※ skill_trees는 문자열이 담긴 배열이다.)

 

skill_trees에 담긴 각 문자열들 중에서, skill의 순서를 따르는 문자열을 골라 그 개수를 출력하는 문제이다.

 

 

문제에 적힌 예시를 적어보면,

 

skill = "CBD" 이고

skill_trees = ["BACDE", "CBADF", "AECB", "BDA"] 일 때

 

ㄱ. BACDE  ==>>  B 스킬을 배우기 전에 C 스킬을 먼저 배워야하므로 규칙에 위배된다.

ㄴ. CBADF  ==>>  규칙에 맞으므로 가능한 스킬트리이다.

ㄷ. AECB     ==>>  규칙에 맞으므로 가능한 스킬트리이다.

ㄹ. BDA       ==>>  B 스킬을 배우기 전에 C 스킬을 먼저 배워야하므로 규칙에 위배된다.

 

따라서, 가능한 스킬트리는 모두 2개이므로 정답은 2가 된다.

 

 

 

내가 푼 방법은 이러하다.

 

문제의 설명에서 입력값은 중복없이 알파벳을 나열한 문자열이라고 하였다.

어차피 중복이 없으므로, 루프당 최고로 수행되는 횟수는 26이다. ( 알파벳은 26개이다. )

 

그렇기에 제일 첫 번째로 생각한 방법은 skill_trees의 각 문자열들에서 불필요한 문자들을 제거한다는 생각을 하였다.

 

중복이 없기때문에 이 방법을 시행한다면, 나중에는 skill에 존재하는 알파벳들만 존재할 것이다. 

 

이렇게 할 경우, 위의 예시에서 skill_trees의 값들은 ["BCD", "CBD", "CB", "BD"] 이렇게 바뀔 것이다.

 

이 방법을 진행하면 skill_trees에 존재하는 값들은 모두 skill에 존재하는 알파벳만 남게 될 것이고

 

중복이 없으므로 skill의 길이보다 작거나 같을 것이다.

 

즉, 인덱스가 같은 부분만 비교한 후 같지 않으면 규칙에 위배되므로 다음 스킬트리로 넘어가는 알고리즘을 만들 수 있다.

 

 

아래는 코드이다.

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int skillSize = skill.size(); //스킬의 개수
    int treeSize = skill_trees.size(); //스킬트리의 개수
    
    int exception = 0; //올바르지 않은 스킬트리의 개수
    
    //불필요한 문자열 제거
    for (int i = 0; i < treeSize; i++) {
        string duplication = "";
        string temp = skill_trees[i];
        int tempSize = temp.size();
        for (int j = 0; j < tempSize; j++) {
            for (int k = 0; k < skillSize; k++) {
                if (skill[k] == temp[j]) {
                    duplication += temp[j];
                }
            }
        }
        skill_trees[i] = duplication;
    }
    
    //문자열 비교
    for (int i = 0; i < treeSize; i++) {
        string temp = skill_trees[i];
        int tempSize = temp.size();
        
        for (int j = 0; j < tempSize; j++) {
            //같은 인덱스 값이 같지 않을 경우 무조건 규칙에 어긋난다.
            if (temp[j] != skill[j]) {
                exception++;
                break;
            }
        }
    }
    
    answer = treeSize - exception;
    
    return answer;
}