[JAVA] [KAKAO] 자동완성

문제를 쉽게 설명하면

1. go, gone, guild 라는 String 배열이 주어지면 이를 학습시킨다.

2. g를 입력하였을때 go와 gone가 나오므로 한번에 자동완성이 안된다.

3. 하지만 go 까지 하면 문자가 다 ( 자동 ) 완성이 되었다.

4. gon까지 입력시 gon으로 시작하는 문자는 gone 뿐이므로 gone을 완성시켜준다.

5. gu까지 입력시 gu로 시작하는 문자는 guild 이기때문에 guild를 완성시켜준다.

따라서 g + o + g + o + n + g + u 가 되어 7번 입력시 문자가 전부 자동완성 된다.

 

이를 풀기 위해서 지난번에 소개했던 Trie 알고리즘을 썼으며 

1. 문자가 주어지면 Trie 트리를 만들고

2. 다음번에 문자 하나씩 읽으면서 ( 자동 ) 완성이 될때까지 cnt를 증가시켜 주었다.

 

소스 코드가 이해가 잘 되지 않는다면 이전 포스트인 Trie 알고리즘을 읽고 오는 것을 추천한다.

 

변수 명이 마음에 들지 않아 메모리가 여유롭기 때문에 int[] 배열을 썼으나 boolean 배열을 써 메모리를 더욱더 효율적으로 사용할 수 있다.

 

이전 포스트와 다르게 생성자에서 null을 써준 이유는 마지막 글자의 경우 위의 예시에서는 gone과 guild가 되겠다.

이 경우 e와 d 에서는 child를 생성할 필요가 없기 때문에 필요할 경우만 따로 만들어 주는 것을 택했다.

 

 

package kakao;

public class autocomplete {
	
	static class Trie{
		Trie[] child;
		int[] childCnt;
		
		public Trie() {
			this.child = null;
			this.childCnt = null;
		}
	}
	
	public static void main(String[] args) throws Exception{
		int answer = 0;
		String[] words = {"go","gone","guild"};
		Trie root = new Trie();
		Trie node = root;
		String line = "";
		int idx = 0;
		for(int i=0; i<words.length; ++i) {
			node = root;
			line = words[i];
			for(int j=0; j<line.length(); ++j) {
				idx = line.charAt(j)-'a';
				if(node.child == null) {
					node.child = new Trie[26];
					node.childCnt = new int[26];
				}
				if(node.child[idx] == null) {
					node.child[idx] = new Trie();
					node.childCnt[idx] = 1;
				}else {
					node.childCnt[idx]++;
				}
				
				node = node.child[idx];
			}
		}
		int inputSum = 0;
		for(int i=0; i<words.length; ++i) {
			node = root;
			line = words[i];
			inputSum = 0;
			for(int j=0; j<line.length(); ++j) {
				idx = line.charAt(j)-'a';
				inputSum++;
				if(node.childCnt[idx] == 1) {
					break;
				}else {
					node = node.child[idx];
				}
			}
			answer += inputSum;
		}
		System.out.println(answer);
	}
}