[JAVA] [BOJ] 5052. 전화번호 목록 ver.2 Trie

Trie로 검색 혹은 이 글을 보러 오신 분은 전화번호 목록에 대해서 알 것이라고 생각하고 문제 설명은 넘어가겠습니다.

 

그리고 sort의 경우 본인이 구현하셔도 상관없지만

이 글에서 Point의 경우 Trie 이기에 라이브러리를 활용하였습니다.

( 그리고 sort의 경우 해주지 않으면 9112 다음에 911이 들어오면 문제가 발생하여 sort 해주었습니다. )

 

Trie의 개념의 경우 제가 이전에 써두었던 글을 참고하시면 더 이해가 잘 가실 것 같습니다.

글 링크 따윈 저는 상남자니까 걸어두지 않을께요

 

이 문제는 저번 문제와 다르게 번호가 들어왔을때

( 예를 들어, 911 이 입력되었고 다음줄에 9112가 들어오면 )

911 때문에 isTerminal이 true 인 상황에서 현재 자식노드의 2번 이 null 이면 911로 끝난 숫자가 있다는 것이고

그때 NO 를 출력하고 종료하면 됩니다.

 

위가 Key Point고 코드를 보면서 이해하시면 됩니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static class TrieNode{
		TrieNode[] child;
		boolean isTerminal;
		
		public TrieNode() {
			this.child = new TrieNode[10];
			this.isTerminal = false;
		}
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		int n = 0;
		String str = "";
		String[] arr = null;
		TrieNode root = null;
		TrieNode node = null;
		int idx = 0;
		String result = "";
		for(int t=1; t<=T; ++t) {
			n = Integer.parseInt(br.readLine());
			arr = new String[n];
			for(int i=0; i<n; ++i) {
				arr[i] = br.readLine();
			}
			Arrays.sort(arr);
			root = new TrieNode();
			node = root;
			result = "YES";
			breakPoint:
			for(int i=0; i<n; ++i) {
				str = arr[i];
				node = root;
				for(int j=0; j<str.length(); ++j) {
					idx = str.charAt(j) - '0';
					if(node.isTerminal && node.child[idx] != null) {
						result = "NO";
						break breakPoint;
					}
					if(node.child[idx] == null) {
						node.child[idx] = new TrieNode();
					}
					if(j == str.length()-1) {
						node.isTerminal = true;
					}else {
						node = node.child[idx];
					}
				}
			}
			bw.write(result+"\n");
		}
		bw.close();
		br.close();
		
	}

}