[프로그래머스] 스킬트리

문제 설명

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

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

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

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

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 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 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

---

스킬트리 개념을 이용해 스킬을 순서대로 배웠는지 검사하는 문제이다.

string 의 find 함수를 활용해서 풀었다.

 

일단 첫 번째 스킬트리부터 검사한다.

올바른 스킬순서인 "CBD"에서 각 스킬을 언제 배웠는지 검사한다.

"BACDE"를 예로 설명하면 C는 2, B는 0, D는 3번째로 배웠다. 

이 인덱스들이 pos 벡터에 순서대로 {2,0,3}으로 저장된다.

이 pos 벡터를 통해 스킬을 순서대로 배웠는지 검사한다.

 

스킬순서가 잘못된 검사 조건문은 두 개이다.

첫번째 조건문부터 살펴보자.

(pos[k] > pos[k + 1] && pos[k+1] != -1) 이는 만약 뒤의 스킬보다 앞의 스킬을 나중에 배운 경우를 검사하는 것이다.

또한 뒤의 스킬을 배우지 않은 경우 -1을 반환하는데 이런 경우는 제외해야 한다.

이 조건은 C,B 스킬에서 바로 걸린다. pos 벡터를 보면 C는 2, B는 0이다. C보다 B를 먼저 배웠으므로 이 경우는 틀렸다.

 

(pos[k]==-1 && pos[k+1] != -1) 이 조건은 앞의 스킬을 안 배웠는데 뒤의 스킬을 배운 경우이다.

네번째 스킬트리인 "BDA"에서 걸린다.

이 경우 pos 벡터는 {-1, 0, 1}이 될 것이다.

C를 배우지 않아 -1인데 B는 배워서 0이 되었으니 잘못된 경우이다. 

 

이 두 스킬트리를 제외한 나머지는 검사를 잘 통과하고 정답인 2를 반환하게 된다.

순서 검사를 어떻게 할 지 고민했던 문제이다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Programmers/%EC%8A%A4%ED%82%AC%ED%8A%B8%EB%A6%AC.cpp

chosh95/STUDY

C++ 코드

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int solution(string skill, vector<string> skill_trees) {
	int answer = 0;
	
	for (int i = 0; i < skill_trees.size(); i++) {
		vector<int> pos;
		bool isTrue = true;
		for (int j = 0; j < skill.size(); j++)
			pos.push_back(skill_trees[i].find(skill[j]));
		

		for (int k = 0; k < pos.size() - 1; k++) {
			if ((pos[k] > pos[k + 1] && pos[k+1] != -1) || (pos[k]==-1 && pos[k+1] != -1)) {
				isTrue = false;
				break;
			}
		}
		if (isTrue) answer++;
	}


	return answer;
}

int main()
{
	cout << solution("CBD", { "BACDE", "CBADF", "AECB", "BDA" });
}