[알고리즘] 프로그래머스 윈터코딩 스킬트리

안녕하세요 오랜만에 포스팅하는 감자코딩입니다. 기말고사 기간때문에 포스팅을 요새 자주 못하였는데요, 방학을 맞이하여 알고리즘을 꾸준히 시작하려고합니다. 그러면 바로 들어가겠습니다.

 

이번에 알아볼 문제는 프로그래머스 문제중 하나인 "스킬트리" 라는 문제입니다.

 

문제 설명

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

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

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

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

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 2 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

skillskill_treesreturn

CBD

[BACDE, CBADF, AECB, BDA]

2

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

 

문제 접근 방법

1. skill 변수는 우리가 비교의 기준이되는 대상의 문자열
2. skill_tress 변수는 각각의 벡터에 들어 가 있는 string 형태의 문자열입니다.
3. 문제의 조건중에 가장 유심히 보아아할것은 순서대로 스킬들을 배울 수 있는것입니다. 만약 BCD라는 스킬을 배울 때 B라는 스킬을 안배우고 C,D라는 스킬을 배울수 없습니다.
4. 문제의 핵심은 스킬 문자열중에서 순서대로 벡터안의 문자열을 어떻게 비교할 것인가? 입니다.
5. find()라는 함수를 사용하여 그 길이를 반환받은 뒤에 문자열이 들어있는지 확인을 하였습니다.
6. 미리 조건으로 조건을 처리 한 후 check라는 변수로 해당 문자열과 동일한 문자열의 개수를 증가시켜진행하였습니다.

코드 설명

#include <string>
#include <vector>
using namespace std;
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    int tf = 1;
    int check = 0;
    for(int i = 0; i < skill_trees.size(); i++){
        string vec_str = skill_trees[i];
        for(int j = 0; j < vec_str.size(); j++){
            // vec_str[j]와 find_num 비교하기
            int find_num = skill.find(vec_str[j]);
            // 범위에맞지않을 경우 
            if(find_num < 0 || find_num > 30){
                continue;
            }
            // 체크된 개수랑 find()한 개수가 틀릴경우 
            if(find_num != check){
                tf = 0;
                break;
            }
            //동일한 문자가 있을경우 통과하면
            else{
                check++;
            }
        }
        if(tf){
            answer++;
        }
        check = 0;
        tf = 1;
    }
    return answer;
}

 

자세한 사항은 코드로 남겨놓았습니다. 확인해보시면 됩니다. 감사합니다. 감자코딩이였습니다.