[프로그래머스][Summer/Winter Coding(~2018)][C++] 스킬트리

문제

프로그래머스 Summer/Winter Coding(~2018) - 스킬트리 (Level 2)

코딩테스트 연습 - 스킬트리

 

---

문제 풀이

접근 방식

주어진 선행 스킬 순서를 만족하는 스킬 트리의 개수를 구하는 문제이다.

 

우선, 선행 스킬 순서를 만족하는지 확인하기 위해 idx 벡터를 만들었다.

이 벡터에 각 스킬 트리마다 선행 스킬이 위치하는 인덱스를 저장해주었다.

스킬 트리에 존재하지 않는 선행 스킬의 경우에는 100을 저장해주었다.

 

이 idx 벡터가 오름차순이어야만 선행 스킬의 순서를 만족하는 스킬 트리가 된다.

그래서 answer에 모든 스킬 트리의 개수를 저장한 후,

idx 벡터가 오름차순이 아닌 스킬 트리인 경우 1씩 감소시키며 최종적인 답을 구해주었다.

 

---

풀이 코드 - C++

#include <string>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
    int st_len = skill_trees.size();
    int skill_len = skill.size();
    int answer = st_len;
    for(int i = 0; i < st_len; i++){
        vector<int> idx(skill_len);
        for(int j = 0; j < skill_len; j++){
            idx[j] = skill_trees[i].find(skill[j]);
            
            // 존재하지 않는 경우
            if(idx[j] == -1)    
                idx[j] = 100;
            
            // idx 벡터가 오름차순이어야 함
            if(j - 1 < 0) continue;
            if(idx[j - 1] > idx[j]){
                answer--;
                break;
            }
        }
    }
    return answer;
}

실행 결과

실행 결과 : 통과 (100.0)