스킬트리 문제풀이(C++, 서머코딩/윈터코딩)[프로그래머스 Lv2]

안녕하세요 멍청한 토끼입니다.

이번 문제는 프로그래머스의 모든문제에 있는

서머코딩/윈터코딩에 LV2에 해당하는

스킬트리 문제 입니다.

포스팅을 시작하겠습니다.

 

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리 | 프로그래머스

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

---

1. 문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

 

문제!!

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

 

제한사항

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

 

예시

Skill	Skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

 

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

 

 

---

2. 문제풀이

이번 문제는 효율성테스트가 없으므로 단순하게 비교해서 진행할 수 도 있습니다. 예를 들어서 3중포문 같이말이죠 그렇지만 저희는 효율성을 올리기 위해 해시자료구조를 이용해서 풀어보도록 하겠습니다. 기본 선행 스킬트리를 해쉬(map)에 순서를 저장 합니다.   예를 들어서 CBD라고 하면 1. C는 1번, B는 2번, D는 3번입니다. 이후 스킬트리를 순회합니다. Count라는 변수를 1로두고 시작을 합니다.   2-1. BACDE라는 스킬트리가 나왔습니다. 해쉬맵에 B를넣고 탐색을하니 2가 나왔습니다. 현재 Count보다 크므로 불가능한 스킬트리입니다.   2-2. CBADF라는 스킬트리가 나왔습니다. 해쉬맵에 C를 넣고 탐색하니 1이 나왔습니다. 현재 Count와 일치하므로 Count를 증가시킵니다. 해쉬맵에 B를 넣고 탐색하니 2가 나왔습니다. 역시 Count와 일치하니 Count를 증가시킵니다. 해쉬맵에 A를 넣으니 0이 나왔습니다.(아무것도 값을 넣어주지 않으면 0으로 시작합니다.) Count보다 작으므로 계속 진행합니다. D를 검색하면 3이나오고 Count와 일치하므로 증가시킵니다. F를 검색하니 0이나오고 Count보다 작으므로 진행합니다. 모두 통과했으므로 answer를 증가시킵니다. 다른문제 또한 반복합니다.

---

3. 소스코드

3.1 주석없는 코드

#include <vector>
#include <map>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, int> tree;
    for (int i = 0; i < skill.length(); i++)
        tree[skill[i]] = i + 1;
    for (auto skt : skill_trees) {
        int count = 1;
        bool check = true;
        for (int i = 0; i < skt.length(); i++) {
            if (tree[skt[i]] > count) {
                check = false;
                break;
            }
            else if (tree[skt[i]] == count)
                count++;
        }
        if (check)
            answer++;
    }
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <map>
 
using namespace std;
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, int> tree;
    //해쉬맵에 스킬순서를 저장
    for (int i = 0; i < skill.length(); i++)
        tree[skill[i]] = i + 1;
    //스킬트리 순회하기
    for (auto skt : skill_trees) {
        int count = 1;
        bool check = true;
        //현재 스킬이 스킬트리에 위배되는지 확인
        for (int i = 0; i < skt.length(); i++) {
            //스킬순서가 맞지않다면 탈출
            if (tree[skt[i]] > count) {
                check = false;
                break;
            }
            //최소 스킬트리를 익혔다면 다음스킬을 익힐수있도록 증가
            else if (tree[skt[i]] == count)
                count++;
        }
        //이상잆어 통과했다면 모든 스킬을 배울수있으므로 카운트 증가
        if (check)
            answer++;
    }
    return answer;
}

3.3 테스트 코드 추가

#include <string>
#include <vector>
#include <iostream>
#include <map>
 
using namespace std;
 
 
int solution(string skill, vector<string> skill_trees) {
    int answer = 0;
    map<char, int> tree;
    //해쉬맵에 스킬순서를 저장
    for (int i = 0; i < skill.length(); i++)
        tree[skill[i]] = i + 1;
    //스킬트리 순회하기
    for (auto skt : skill_trees) {
        int count = 1;
        bool check = true;
        //현재 스킬이 스킬트리에 위배되는지 확인
        for (int i = 0; i < skt.length(); i++) {
            //스킬순서가 맞지않다면 탈출
            if (tree[skt[i]] > count) {
                check = false;
                break;
            }
            //최소 스킬트리를 익혔다면 다음스킬을 익힐수있도록 증가
            else if (tree[skt[i]] == count)
                count++;
        }
        //이상잆어 통과했다면 모든 스킬을 배울수있으므로 카운트 증가
        if (check)
            answer++;
    }
    return answer;
}
 
void print(string skill, vector<string> skill_trees, int answer) {
    int t = solution(skill, skill_trees);
    if (answer == t)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main() {
    print("CBD", {"BACDE", "CBADF", "AECB", "BDA"}, 2);
    return 0;
}

4. 결과