[Lv2] 스킬트리

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

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

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

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

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

제한 조건

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

---

skill에 있는 스킬만 특수스킬이라,

스킬트리 배열 중 저 특수스킬이 아예 없으면 상관없이 가능한 트리고,

하나라도 존재하면, 특수스킬 순서로 익혀야 가능한 트리/아니면 불가능한 트리.

 

char[] skills = skill.toCharArray();
Stack<String> stack = new Stack<>();
int answer = 0;
for(String str:skill_trees) {
	boolean notExist = true;
	for(int i=0;i<skills.length;i++) {
		if(str.indexOf(skills[i])!=-1) {
			notExist = false;
			break;
		}
	}
	if(notExist) answer++;
	else {
		stack.add(str);
	}
}
if(stack.isEmpty()) return answer;

특수 스킬들은 skills에 배열로 저장.

 

주어진 트리 중 indexOf(skills[i])가 -1이면 문자열에 없다는 것이고, 0이상이면 그 위치에 있다는 것.

 

트리마다 스킬들 검색결과가 모두 -1이면, 얘는 상관없이 가능,

 

검색하다가 -1이 아닌 결과가 나오면, 얘는 고려대상으로 저장가능한 곳 아무 곳에나 저장해둠.

(list든 stack이든 queue든..)

 

저장소가 비어있다면 그대로 반환하고 아니면 아래과정까지.

 

while(!stack.isEmpty()) {
	String str = stack.pop();
	int[] index = new int[skills.length];
	for(int i=0;i<skills.length;i++) {
		index[i] = str.indexOf(skills[i]);
	}

저장소에서 아무 문자열이나 꺼내주고,

 

특수 스킬만큼 칸을 만든 후,(index)

 

꺼낸 문자열에서 각 스킬이 몇번째에 등장하는지 indexOf(skills[i])로 저장해준다.

 

이제 여기서 -1이 한 번이라도 등장했는데, 다음에 0 이상인 칸이 나온다면, 순서대로가 아니므로 불가능 판정.

0이상인 숫자들이 오름차순이다가 마지막 나머지들만 -1이라면, 순서대로 배우다 만 것이므로 가능 판정.

while(!stack.isEmpty()) {
	String str = stack.pop();
	int[] index = new int[skills.length];
	for(int i=0;i<skills.length;i++) {
		index[i] = str.indexOf(skills[i]);
	}
	int prev = -1;
	boolean isOK = true;
	boolean onceNop = false;
	for(int i=0;i<index.length;i++) {
		if(index[i]==-1) {
			onceNop=true;
		}
		else {
			if(onceNop) {
				isOK = false;
				break;
			}
			if(i == 0) {
				prev = index[i];
			} else {
				if(prev > index[i]) {
					isOK = false;
					break;
				} else {
					prev = index[i];
				}
			}
		}
	}
	if(isOK) answer++;
}
return answer;