[C++] 스킬트리

[문제]

코딩테스트 연습 - 스킬트리 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

완탐으로 풀었다. 제한 조건이 string 값들이 모두 26이하이고 skill_trees는 최대 20까지 들어가니 시간 복잡도를 따졌을때 모두 비교를 하더라도 26 * 26 * 20으로 시간안에 충분히 들어올수 있으므로 완탐을 이용해서 풀었다.

[회고]

완탐으로 풀기는 했는데 조금 더 깔끔한 풀이가 없는지 찾아봐야겠다. 충분히 더 깔끔한 풀이가 나올 수 있었던 문제인것 같다.

[코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

//cbd -> skill_trees[i] 로 파악하는게 아니라 skill_trees[i] -> cbd로 파악을 해야 한다.

bool skillTo(string s1, string s2){
    bool answer = true;
    int count = 0;
    for(int i = 0;i<s2.size();i++){
        for(int j = 0;j<s1.size();j++){
            if(s2[i] == s1[j]){
                if(count != j){
                    return false;
                }
                count++;
            }
        }
    }
    
    return answer;
}

int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    
    for(int i = 0;i<skill_trees.size();i++){
        bool flag = true;
        flag = skillTo(skill,skill_trees[i]);
        if(flag){
            answer++;
        }
    }
    
    return answer;
}