프로그래머스[Java] - (Level2)스킬트리

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

프로그래머스

코드

class Solution {
	public static int solution(String skill, String[] skill_trees) {
		int answer = 0;
		for(int i=0; i<skill_trees.length; i++){
			int index = 0;
			boolean check = true;

			String[] skills = skill_trees[i].split("");
			for(String s : skills){
				// skill와 관련없는 문자는 건너뛰기
				if(skill.indexOf(s) == -1)	continue;
				// 스킬 목록과 현재 배워야 하는 스킬의 순서를 비교한다.
				if(index == skill.indexOf(s)) index ++;
					
				/*
				 * 배워야하는 스킬의 순서보다 현재 스킬이 더 앞서나갈때.
				 * e.g) skill = "CBD" , skills = "BACDE" -> C를배우고 B를 배워야함
				 */
				else if(index < skill.indexOf(s)){
					check = false;
					break;
				}
			}
			if(check)	answer ++;
		}
		return answer;
	}
}

풀이

어떻게 접근하지 생각하다가 도저히 떠오르지 않아 블로그를 참고했다.

나는 계속 문제를 잘못 이해하고, 잘못 생각했다.

배워야하는 스킬 순서가 "CBD"일때, CBD, CB, BD, CD 등의 경우가 가능한 줄 알았다.

하지만 B를 배우려면 C를 배워야하고, D를 배우려면 CB를 배워야하므로 가능한 경우의 수는 CBD, CB, C 뿐이다.

위 풀이는 주어진 skill_trees 배열의 각 요소별로 배워야하는 스킬과 순서를 비교하면서 푸는 방식이다.

String.indexOf(String str) 메소드의 경우, 해당 문자열에서 매개변수의 문자가 몇번째 인덱스인지 찾는 메소드이다.

만약 찾고자 하는 문자가 없을경우 -1을 반환한다.

https://docs.oracle.com/javase/8/docs/api/

 

skill_trees의 각 요소를 split을 기준으로 잘라서 문자별로 비교한다.

e.g) "BACDE" = > 'B', 'A', 'C', 'D', 'E'

String[] skills = skill_trees[i].split("");

 

그 후 자른 문자열을 모두 탐색하면서 배워야하는 스킬과 비교한다.

1) 현재 문자가 배워야하는 스킬과 관련이 없는경우(indexOf가 -1을 리턴하는경우) -> 건너띈다.

 

2) 스킬을 배우기 위해선 반드시 첫번째(C, 인덱스 = 0) 스킬을 배워야 한다. 

따라서 해당 스킬을 배웠을경우, index값을 증가시켜 다음 배워야하는 스킬과 비교한다.

 

3) 현재 배워야하는 스킬보다 현재 스킬이 더 앞설때.

e.g) 현재 C(인덱스 = 0)스킬을 배워야하는데, 현재 스킬이 B(인덱스 = 1) 또는 D(인덱스 = 2)일때,

불가능한 스킬트리 이므로 뒤는 더 탐색할 필요도 없이 불가능한 스킬이다.