<프로그래머스> Level2 스킬트리

스킬 트리

문제

문제 설명

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

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

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

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

제한 조건

스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

스킬 순서와 스킬트리는 문자열로 표기합니다.

예를 들어, C → B → D 라면 CBD로 표기합니다

선행 스킬 순서 skill의 길이는 2 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.

skill_trees는 길이 1 이상 20 이하인 배열입니다.

skill_trees의 원소는 스킬을 나타내는 문자열입니다.

skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

문제 풀이

스킬 트리의 문제에서 주어진 조건들을 정리하자면 (skill_trees의 문자열들을 s라고 한다):

1. "CBD"라면 s들에 'C' 가 없을떄 'B'와 'D'는 있어선 안된다. 즉 s 에서 "CBD'를 제외한 다른 문자를 삭제 했을때  'C', 'CB','CBD' 만 가능하다
2. "CBD"일때 s에 "CBD"가 하나도 없다면 가능한 스킬트리이다

나는 skill의 문자 하나하나를 각 s에서 찾아 위치와 문자를 pair형태로 저장 했다. 이때 'CBD'가 없으면 answer 카운트를 올려준다. 그 다음 위치를 기준으로 정렬한다음 skill의 문자의 순서와 pair형태에서의 문자의 순서를 비교한다. 이때 기준은 pair형태의 문자들이다. 

C++ 코드

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    vector<vector<pair<int,char>>> new_skill_trees;
    for (auto s : skill_trees){
        vector<pair<int,char>> temp;
        for (char &c : skill){
            if(s.find(c)!=string::npos){        //문자가 문자열에 존재할 경우
                temp.push_back(make_pair(s.find(c),c));
            }
        }
        if(temp.empty()){       //skill에 있는 스킬들이 하나도 없을때
            answer++;
        }else{
            new_skill_trees.push_back(temp);
        }
    }
    
    for(auto a : new_skill_trees){
        sort(a.begin(),a.end());
       int i;
        for(i=0;i<a.size();i++){        //skill 과 a를 비교할때 기준을 a로한다.
            if(skill[i]!=a[i].second)  break;
        }
        if(i==a.size()){
            answer++;
        }
    }
    return answer;
}

다른 사람의 풀이를 보던중 더 깔끔한 코드가 있어서 가지고 와봤다.  주석을 이해를 돕기 위해 내가 달았다.

#include <string>
#include <vector>
 
using namespace std;
 
bool tree_check(const string& tree, const string& skill) {
    bool broken = false;
    size_t prev = 0;        //size_t 어떤 객체나 값이 포함할 수 있는 최대 크기의 데이터를 표현하는 타입
    for (auto s : skill) {
        size_t cur = tree.find(s);    //s의 값을 현재 위치로
        if (cur != string::npos) {
            if (broken ||
                cur < prev)        //현재의 위치가 이전의 위치보다 뒤인경우, 즉 skill의 순서를 
                return false;
            else
                prev = cur;
        } else broken = true;    //skill의 첫번쨰 스킬이 없는경우, 이때는 skill의 두번쨰 스킬이 들어오면 바로 false를 return
    }
    return true;
}
 
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    for (auto tree : skill_trees) {
        if (tree_check(tree, skill)) ++answer;
    }
 
    return answer;
}