[Java] 2020 카카오 공채 코딩테스트 문제 : 가사 검색(자료구조/ Trie 자료구조)

--- 문제 ---

 

2020 KAKAO BLIND RECRUITMENT : 가사 검색

 

제시된 단어들 중 에서, 원하는 단어와 조건이 맞는 경우의 수를 세는 문제

 

정확도와 효율성을 둘 다 본다는 특징이 있는 문제였습니다.

 

 

--- 코드 ---

 

문제를 보고 처음에 딱 든 생각은 완전탐색 이었습니다.

queries 에 있는 단어들을 하나씩 가져와서 words에 있는 길이가 같은 단어들을 모두 검사하는 방식 입니다.

정확도에서는 만점을 받았지만, 역시나 효율성에서 막혔습니다 ㅠㅠ

 

그래서 어떤 방법이 좋을까 생각하다가,  카카오 페이지에 올라와있는 해설을 보게되었습니다.

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

Trie(트라이) 라는 자료구조를 사용하면 풀 수 있다는 말이었습니다!

여기서 Trie 구조란 ? 문자열에 특화된 트리 구조로, 문자 하나씩 깊이가 추가되는 구조인데 그림으로 보면 아래와 같습니다.

 

Trie 구조 예시

위와 같이, 한글자씩 트리를 추가해가는 구조입니다. 같은 구간에 중복되는 문자가 있으면, 

그 문자에 같이 포함을 시켜 count 를 추가해가는 구조로 이 문제를 풀면 됩니다.

 

코드는 아래와 같습니다.

 

import java.util.Arrays;

public class Prob4 {

	public static void main(String[] args) {
		String[] words = { "a","b","frodo", "front", "frost", "frozen", "kakao", "frame" };
		String[] queries = { "?","fro??", "????o", "fr???", "fro???", "pro??", "??ont", "????o" };
		
		int[] answer = new int[queries.length];
		
		// 접미사(subffix)용 트라이 구조
		Trie[] tries = new Trie[10001]; 
		// 접두사(prefix)용 트라이 구조
		Trie[] rtries = new Trie[10001];
		
		// words 길이 별 분류
		for(String word : words) {
			int size = word.length();
			// 길이에 해당하는 트라이 만들기
			try {
				tries[size].insert(word.toCharArray());
			}catch(Exception e) {
				tries[size] = new Trie();
				tries[size].insert(word.toCharArray());
			}
			
			// 반대 문자도 트라이 생성
			word = (new StringBuffer(word)).reverse().toString();
			try {
				rtries[size].insert(word.toCharArray());
			}catch(Exception e) {
				rtries[size] = new Trie();
				rtries[size].insert(word.toCharArray());
			}
		}
		
		// trie 이용하여 해당 쿼리에 맞는 갯수들 찾기
		for(int i=0; i<queries.length; ++i) {
			String query = queries[i];
			if(query.indexOf('?')==0) {
				// prefix
				try {
					query = (new StringBuffer(query)).reverse().toString();
					answer[i] = rtries[query.length()].search(query.toCharArray());
				}
				catch(Exception e) {
					continue;
				}
			}
			
			else {
				// suffix
				try {
					answer[i] = tries[query.length()].search(query.toCharArray());
				}
				catch(Exception e) {
					continue;
				}
			}
		}
		
		System.out.println(Arrays.toString(answer));

	}

}

// Trie Node
class Trie {

	int count;
	Trie[] childList;

	Trie() {
		childList = new Trie[26];
		count = 0;
	}

	void insert(char[] word) {
		Trie current = this;
		for (char no : word) {
			++current.count;
			if (current.childList[no - 'a'] != null) {
				current = current.childList[no - 'a'];
			} else {
				current.childList[no - 'a'] = new Trie();
				current = current.childList[no - 'a'];
			}
		}
	}

	int search(char[] query) {
		Trie current = this;
		for (char no : query) {
			if (no == '?') {
				return current.count;
			}

			if (current.childList[no - 'a'] != null) {
				current = current.childList[no - 'a'];
			} else {
				return 0;
			}
		}
		return current.count;
	}

}

 

--- 출처 ---

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

코딩테스트 연습 - 가사 검색 | 프로그래머스