[Programmers/Summer,Winter Coding 2018] 스킬트리 - Java

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 스킬트리

 

 

문제 링크

 

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

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

 

 

문제 풀이

 

Queue를 사용하여 skill 순서를 판별한다.

한 단어 끝날 때마다 skill_q를 초기화해준다.

 

 

스킬 순서대로 푸는 것이 이 문제의 핵심이다. 제목에서 나왔듯이 트리 알고리즘이란 것을 사용하면 훨씬 더 효율적이고 쉽게 풀 수 있을 것이다. 하지만 나는 아직 트리 알고리즘을 공부해본 적 없어서 그냥 내 지식대로 풀었다. 다음에 시간 날 때 트리 알고리즘을 공부해야겠다고 다짐하게 된 계기다. skill_trees는 무조건 순서대로 해야 하므로 Queue를 이용했다. peek()과 같지 않다면 순서대로가 아니므로 다음으로 넘어간다. 이렇게 풀면 문제가 skill 이 모두 들어있어야만 다음에도 오류가 없는데 그걸 맞춰주기 위해 count를 사용하여 한 단어가 끝날 때마다 초기화해줬다.

public static int solution(String skill, String[] skill_trees) {
	int answer = 0;
	int count = skill.length();
	Queue<Character> skill_q = new LinkedList<>();
	
    for(int i = 0; i < skill.length(); i++) {
		skill_q.add(skill.charAt(i));
	}

	outer : for(int i = 0; i < skill_trees.length; i++) {
		if(count != skill.length()){
			for(int k = count; k > 0; k--) {
				skill_q.add(skill_q.poll());
			}
			count = skill.length();
		}

		for(int j = 0; j < skill_trees[i].length(); j++) {
			if(skill.contains(Character.toString(skill_trees[i].charAt(j)))){
				if(skill_trees[i].charAt(j) != skill_q.peek()) {
					continue outer;
				}
				skill_q.add(skill_q.poll());
				count--;
			}
		}
		answer++;
	}
	return answer;
}