[BOJ-5052][트라이] 전화번호 목록 -Java

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class boj_5052_전화번호목록 {
	static class TrieNode{
		HashMap<Character, TrieNode> childNodes=new HashMap<>();
		boolean isLastChar;
		
		//childNodes얻기
		public HashMap<Character, TrieNode> getChildNodes(){
			return this.childNodes;
		}
		
		public void setIsLastChar(boolean isLastChar) {
			this.isLastChar=isLastChar;
		}
		
		public boolean getIsLastChar() {
			return this.isLastChar;
		}
	}
	static class Trie{
		TrieNode rootNode;
		
		public Trie() {
			rootNode = new TrieNode();
		}
		
		public boolean insert(String word) {
			int len=0;
			TrieNode thisNode = this.rootNode;
			for(int i=0; i<word.length(); i++) {
				if(thisNode.getChildNodes().containsKey(word.charAt(i))) { //만약 다음꺼 가지고 있으면
					len++; //포함하고 있다고 하나 올려주고 
				}
				else { //만약에 다음꺼 없으면 ?
					thisNode.getChildNodes().put(word.charAt(i), new TrieNode()); //새로운 글자 하나 넣어주고
				}
				thisNode=thisNode.getChildNodes().get(word.charAt(i)); //this는 다음꺼 바라보게
				
			}
			
			return (len==word.length())? false : true;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T=Integer.parseInt(br.readLine());
		
	loop:for(int tc=0; tc<T; tc++) {
			Trie trie = new Trie();
			int n=Integer.parseInt(br.readLine());
			String phoneNumbers[]= new String[n];
			for(int i=0; i<n; i++) {
				phoneNumbers[i]=br.readLine();
			}
			
			Arrays.sort(phoneNumbers, (o1,o2)->(o2.length()-o1.length())); //길이가 긴 순으로 정렬
			
			for(int i=0; i<n; i++) {
				if(!trie.insert(phoneNumbers[i])) {
					bw.write("NO"+"\n");
					continue loop;
				}
			}
			bw.write("YES"+"\n");
			
		}
		bw.flush();
		
	}

}

소요시간 : 30분

 

우선 제목에 적혀있듯이 트라이를 사용해서 풀었습니다.

 

트라이를 사용하기 위해 전화번호 목록을 전화번호 길이의 내림차순으로 정렬했습니다.

그래야지 가장 긴것을 넣고 그다음 것부터 넣으면서 글자가 겹치는지 안 겹치는지 확인할 수 있기 때문입니다.

 

그리고 insert함수에서 겹치는 글자의 갯수와 현재 입력으로 들어온 글자의 개수가 같다면

모든 글자가 겹치는것이기 때문에 NO를 출력해줍니다.

모든 전화번호목록이 안 겹친다면 YES를 출력하면 되겠죠?

 

끝~