백준 5052 전화번호 목록 (JAVA)

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

5052번: 전화번호 목록

 

저는 트라이를 통해서 해당 문제를 해결하였습니다.

트라이를 통해서 해당 문자열의 prefix가 처음 나왔는지 탐색하였습니다.

저는 들어오는 순서대로 prefix가 있는지 판단하는 건 줄 알고 정렬을 하지 않고 계속 트라이를 통해 확인하여 틀렸습니다. 이를 정렬하여 트라이에 넣어서 문제를 해결하였습니다.

 

 

package BOJ.Tree;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_5052 {
    private static class Tree{
        boolean end = false;
        Tree[] leaf = new Tree[10];

        public boolean insert(String str , int depth){
            if(this.end){
                return false;
            }
            if(str.length() == depth){
                this.end = true;
                return true;
            }
            int now = str.charAt(depth) - '0';
            if(leaf[now] == null){
                leaf[now] = new Tree();
            }
            return leaf[now].insert(str,depth+1);
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int test = stoi.apply(st.nextToken());
        for(int t = 0 ; t < test ; t++){
            Tree tree = new Tree();
            boolean flag = true;
            st = new StringTokenizer(br.readLine()," ");
            int n = stoi.apply(st.nextToken());
            String[] input = new String[n];
            for(int i = 0 ; i < n ; i++){
                String now = br.readLine();
                input[i] = now;
            }
            Arrays.sort(input);
            for(int i = 0 ; i < n ; i++){
                if(flag && !tree.insert(input[i],0)){
                    flag = false;
                }
            }

            if(flag){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }
    }
}