[Backjoon] 5052번 전화번호 목록

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

class Main {
    static class Node{
        int n;
        int depth;
        boolean isLast = false;
        Node[] child;
        Node(int n, int depth){
            this.n = n;
            this.depth = depth;
            child = new Node[10];
        }

        void inputChild(Node n, int idx){
            child[idx] = n;
        }

        void checkLast(){
            this.isLast = true;
        }

        boolean isLast(){
            return isLast; 
        }

        boolean isNext(int n){
            if(child[n] == null)
                return false;
            return true;
        }

        Node nextNode(int n){
            return child[n];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int testNum = Integer.parseInt(br.readLine());
        for(int i = 0; i < testNum; i++){
            int phoneNum = Integer.parseInt(br.readLine());
            String[] arr = new String[phoneNum];

            for(int j = 0; j < phoneNum; j++){
                arr[j] = br.readLine();
            }

            Arrays.sort(arr, new Comparator<String>(){
                public int compare(String s1, String s2){
                    return s1.length() - s2.length();
                }
            });
            Node start = new Node(-1, 0);
            String answer = "YES";
            for(String s : arr){
                Node n = start;
                int depth = 1;
                while(depth <= s.length()){
                    int nextNum = s.charAt(depth-1) - '0';
                    if(n.isLast()){
                        answer = "NO";
                        break;
                    }
                    if(!n.isNext(nextNum)){
                        n.inputChild(new Node(nextNum, depth), nextNum);
                    }
                    n = n.nextNode(nextNum);
                    depth++;
                }
                if(answer.equals("NO")){
                    break;
                }
                n.checkLast();
            }
            sb.append(answer + "\n");
        }
        System.out.println(sb.toString());
        br.close();
    }

}
​

정렬 후 앞문자와 비교하는 방식을 사용했다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Comparator;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        String[] answer = new String[t];
        Arrays.fill(answer, "YES");
        ArrayList<String[]> list = new ArrayList<>();
        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            String[] array = new String[n];
            for(int j = 0; j < n; j++){
                array[j] = String.valueOf(br.readLine());
            }
            list.add(array);
        }
        for(int i = 0; i < t; i++){
            String[] array = list.get(i);
            int n = list.get(i).length;
            HashMap<String, Integer> hashmap = new HashMap<>();

            Arrays.sort(array, new Comparator<String>() {
                public int compare(String s1, String s2) {
                    return s1.length() - s2.length();
                }
            });
            for (int j = 0; j < n; j++) {
                for(int k = 1; k < array[j].length(); k++){
                    String s = array[j].substring(0, k);
                    if(hashmap.containsKey(s)){
                        answer[i] = "NO";
                        break;
                    }
                }
                if(answer[i].equals("NO")){
                    break;
                }else{
                    hashmap.put(array[j], n);
                }
            }
            System.out.println(answer[i]);
        }
        br.close();
    }
}

트라이를 사용해서 구현했다