[Java 알고리즘] 프로그래머스, 스킬트리

스킬트리

 

문제 설명

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

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

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

선행 스킬 순서 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 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

 

나의 풀이

class Solution {
    public int solution(String skill, String[] skill_trees) {
        		int answer = 0;
		
		int index = 0;
		while(true) {
			String skill_tree = skill_trees[index];
			String skill_clone = new String(skill_tree);
			int size = skill_tree.length();
			for (int i =0; i < size; i++) {
				String oneSkill = String.valueOf(skill_clone.charAt(i));
				if (!skill.contains(oneSkill)) {
					skill_tree = skill_tree.replace(oneSkill, "");
				}
			}
			if (skill.indexOf(skill_tree) == 0) {
				answer++;
			}
			index++;
			if(index == skill_trees.length) break;
		}
	
		return answer;
    }
}

처음 문제를 보자마자 생각이 든것은 replace 였다. 남들은 어떻게 queue나 다른 자료구조를 이용해서 풀었을 지 모르지만.. 메이플스토리라는 게임을 통해 스킬트리 검색을 밥먹듯이 하던 나에게는 문제를 이해하는데 크게 어려움을 느끼지 않았다. 일단 스킬트리 string이 주어졌을 때, 선행 스킬이 존재하지 않는 스킬들은 모두 빈문자열("")로 replace 처리해주었다. 

 

그렇게 되면 만약 CBAD -> replace -> CBD가 되죠. 그런데 indexOf == 0을 사용한 이유가 다음의 경우 때문입니다.

 

ACB -> replace -> CB , 즉, 스킬트리는 선행스킬이 무조건 있는 경우에만 올바른 스킬트리인 것이므로 B가 있기위해서는 C가 무조건 있어야하므로 CBD 순서에서 C/ CB/ CBD 이렇게 세가지가 있습니다. 이들은 모두 indexOf 한 결과가 0일 것이기 때문에 이 점을 착안하여 indexOf를 썼습니다.