[Programmers] Level 2. 스킬트리 (2018 윈터코딩 / C++)

정리

선행 스킬 순서에 맞춰 스킬을 올려야 가능한 스킬트리가 되고 그렇지 않으면 불가능한 스킬트리가 된다.
그래서 나는 다음과 같이 풀었다. 그런데 너무 지저분하게 풀은 느낌이 있다.
누군가 더 보기좋고 깔끔하게 풀지 않았을까? 그래서, 나는 이렇게 풀어보았다.

1) 유저가 만든 스킬트리 (skill_trees) 에서 선행스킬만 따로 뽑았다.
2) 유저 스킬트리에서 뽑은 선행스킬(check)과 스킬 트리 순서(skill)과 비교했다.
3) 선행 스킬(i)이 일치했을 때 먼저 배워야 하는 선행 스킬(i-1)이 있는지 비교했다.
4) bool 형을 이용해서 선행 스킬(i) 가 있지만 먼저 배워야 하는 선행 스킬(i-1)이 없다면 false, 있다면 true.
5) 비교 결과 가능하다면 카운트를 증가시켜줘서 가능한 스킬트리 갯수를 출력한다.

이렇게 풀었지만 처음에 실수했던 부분이 for문을 여러개 돌려서 시간초과가 났었다.
최대한 시간복잡도를 적게 해주는 방향으로 풀다보니 위와 같이 풀게 되었다.

소스코드

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    vector<char> check;
    
    for(int i=0; i<skill_trees.size(); i++){
        for(int j=0; j<skill_trees[i].size(); j++){
            for(int k=0; k<skill.size(); k++){
                if(skill_trees[i][j] == skill[k]){
                    check.push_back(skill_trees[i][j]);
                    break;
                }
            }
        }
        
        bool poss = true;
        
        for(int i=0; i<check.size(); i++){
            for(int j=0; j<skill.size(); j++){
                if(check[i] == skill[j]) {
                    if(check[i-1] != skill[j-1]) {
                        poss = false;
                        break;
                    }
                }
            }
        }
        printf("\n");
        check.clear();
        
        if(poss) answer++;
    }
    
   
    return answer;
}