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

문제 링크

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

풀이 과정

트라이 자료구조로 해결할 수 있는 문제입니다. 입력받은 문자열을 검색할 때, 검색이 끝났음에도 자식 노드가 남아있으면, 일관성 없는 목록으로 판단할 수 있습니다.

위 트라이 구조에서, 문자열 911 을 검색했을 때 단말 노드(가장 아래쪽 파란색 노드)에서 더 이어지는 자식 노드(2를 문자로 갖는 노드)가 존재합니다. 이러면, 문자열 911 을 접두사로 갖는 문자열이 존재한다는 의미이며, 문제에서 말하는 일관성이 없는 목록에 해당됩니다.

private boolean find(String str) {
    TrieNode current = root;
    int len = str.length();

    for (int i = 0; i < len; i++) {
        char ch = str.charAt(i);
        int idx = ctoi(ch);
        current = current.children[idx];
    }

    return current != null && current.isTerminal && current.childCnt == 0;
}

트라이 노드 각각은 자식 노드의 개수를 저장하고 있습니다. 따라서 단말 노드에 위치했을 때 current.childCnt == 0 이면, 해당 단어를 접두사로 갖는 단어가 존재하지 않는다는 것을 의미하며 , true를 리턴합니다.

이와 반대로 current.childCnt != 0 이면, 해당 단어를 접두사로 갖는 단어가 존재한다는 것을 의미하며, false를 리턴합니다. 이 경우, 목록의 일관성을 해치게 됩니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();
        for (int tc = 1; tc <= TC; tc++) {
            boolean answer = true;
            Trie trie = new Trie();

            int n = sc.nextInt();
            String[] inputs = new String[n];

            for (int i = 0; i < n; i++) {
                trie.insert(inputs[i] = sc.next());
            }

            for (String input : inputs) {
                if (!trie.find(input)) {
                    answer = false;
                    break;
                }
            }

            System.out.println(answer ? "YES" : "NO");
        }
    }

    private static class Trie {
        TrieNode root = new TrieNode();

        private void insert(String str) {
            TrieNode current = root;
            int len = str.length();

            for (int i = 0; i < len; i++) {
                char ch = str.charAt(i);
                int idx = ctoi(ch);

                if (current.children[idx] == null) {
                    current.children[idx] = new TrieNode();
                    current.childCnt++;
                }

                current.children[idx].value = ch;
                current = current.children[idx];
            }

            current.isTerminal = true;
        }

        private boolean find(String str) {
            TrieNode current = root;
            int len = str.length();

            for (int i = 0; i < len; i++) {
                char ch = str.charAt(i);
                int idx = ctoi(ch);
                current = current.children[idx];
            }

            return current != null && current.isTerminal && current.childCnt == 0;
        }
    }

    private static class TrieNode {
        TrieNode[] children = new TrieNode[10];
        char value;
        boolean isTerminal;
        int childCnt;
    }

    private static int ctoi(char ch) {
        return ch - '0';
    }
}