프로그래머스 Level2 스킬트리 JAVA

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

코딩테스트 연습 - 스킬트리

 

처음에 이 문제를 풀 때 3중포문으로 접근했다.  3중포문을 사용하면 시간복잡도가 오래걸릴 뿐만 아니라 코드를 읽는 입장에서도 매우 힘든일이다.

 

1. 문제 첫 접근

 - for문을 3개를 돌려서, 잡스킬(예제에서는 C,B,D 를 제외한 스킬들) 을 모두 제거해주었다.

 -잡스킬을 제거한 다음에 예제(C->B->D)  순서에 알맞는지 검사하였다.

통과는 되었지만 3중 for문을 2개나 사용하였고, 가독성도 떨어질 뿐만 아니라 단순 노가다성 알고리즘 같았다.

 

2. 문제 두번째 접근

*indexOf 메소드

->indexOf() 는 특정 문자나 문자열이 앞에서부터 처음 발견되는 인덱스를 반환하며

만약 찾지 못했을 경우 "-1"을 반환

 

indexOf 메소드를 사용하여 접근하였다.

1. 예제에서 주어진 C->B->D 를 기준으로 , C의 인덱스는 0 , B의 인덱스는 1, D의 인덱스는 2 가 된다.

index 변수를 선언하여 C부터 선행해야하는 스킬이므로 , index=0으로 초기화해준다.

 

2. 정상적인 스킬트리 (C->B->D) 와 주어진 스킬트리를 indexOf를 통해 비교한다.

-> 만약, ACDB 라는 스킬트리가 주어진다면 CBD에는 A가 포함되어있지 않기때문에 '음수'를 반환한다. call 2( j=0)

->음수 반환은 조건문 어디에도 속하지 않는다.  다음 call 1( j = 1) 로 넘어간다.

->다음은 C다. CBD에 C가 포함된다.  CBD에서 C는 첫번째자리인 0번째 인덱스에 있으므로, else if 조건에 걸린다. 조건에 걸리면 다음 스킬을 탐색하기위해 index를 ++ 해준다.  

 

-> 다음은 D다.  CBD 에서 는 2번째 인덱스에 위치해있는데, 현재 인덱스는 B(index =1 ) 을 가르키고 있다. 따라서 2를 리턴하게 된다.  if 조건에 성립하므로, 이 스킬트리는 사용이 불가능 하는 뜻이다. call2 (j=2)

 

 

class Solution {
  public int solution(String skill, String[] skill_trees) {
		int answer = 0;

		for (int i = 0; i < skill_trees.length; i++) {
			String[] s = skill_trees[i].split("");
			int index = 0;
			boolean ck = true;

			for (int j = 0; j < s.length; j++) {
				if (index < skill.indexOf(s[j])) {
					ck = false;
					break;
				} else if (index == skill.indexOf(s[j])) {
					index++;
				}
			}

			if (ck) {
				answer++;
			}
		}
		return answer;
	}
}