[백준] 5052번 전화번호 목록

문제 설명

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

문제 풀이

• trie 자료구조를 이용하여 풀이하였다.
• 우선 문자열들을 길이순으로 정렬해주어야한다. (길이가 짧은 문자열을 먼저 넣어야 판별가능)
• 특정 문자열을 넣어줄때 마다 해당 문자열의 가능한 subString(abcd -> a, ab, abc, abcd)을 모두 trie에서 검색하여 존재한다면 일관성 없는 문자열로 판별해준다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int T, N;
    public static String[] arr;

    public static class Node {
        Map<Character, Node> child = new HashMap<>();
        Boolean isEnd = false;
    }

    public static class Trie {
        Node root = new Node();

        public void insert(String input) {
            Node node = this.root;

            //자식 노드 존재하면 해당 노드 리턴, 없으면 map에 해당 char을 key로 추가하여 새로운 노드 생성
            for (int i = 0; i < input.length(); i++)
                node = node.child.computeIfAbsent(input.charAt(i), k -> new Node());

            node.isEnd = true;
        }

        public boolean search(String input) {
            Node node = this.root;

            //해당 char 노드 존재하면 이동, 없으면 false 리턴
            for (int i = 0; i < input.length(); i++) {
                node = node.child.getOrDefault(input.charAt(i), null);

                if (Objects.isNull(node))
                    return false;
            }

            //마지막 글자가 노드에 도달하더라도 해당 문자열의 마지막 단어가 아닐 수 있음
            //마지막인지 여부를 가지고 String 존재하는지 판별
            return node.isEnd;
        }
    }
    public static void solve() throws IOException {
        Trie trie = new Trie();
        Boolean result = true;

        //input 길이 순으로 정렬
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });

        for (int i = 0; i < N; i++) {
            String in = arr[i];
            if (!result) continue;
            for (int j = 1; j <= in.length(); j++) {
                String sub = in.substring(0, j);
                if (trie.search(sub)) {
                    result = false;
                    break;
                }
            }
            trie.insert(in);
        }
        if (result) bw.write("YES\n");
        else bw.write("NO\n");
    }

    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out)) ;
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            arr = new String[N];
            for (int i = 0; i < N; i++)
                arr[i] = br.readLine();
            solve();
        }
        bw.flush();
        bw.close();
        br.close();
    }
}