백준 - 5052 전화번호 목록(Java)

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

5052번: 전화번호 목록

 

트라이(Trie) 문제입니다.

 

트라이는 문자열 트리를 만들어서 문자가 존재하는지 확인할 수 있는 자료구조입니다.

트라이는 크게 두 가지의 메소드가 존재합니다.

1. 삽입(insert) : 문자열을 넣어 트리로 만듦
2. 검색(search) : 문자열을 검색

문자열 ["123", "124", "245", "1234"]를 트라이로 구현하면 다음 그림과 같습니다.

 

각 문자열을 삽입할 때, 그림과 같이 마지막 문자에 end로 표시합니다.

 

문제로 돌아가볼까요?

일단 트라이를 만들고, 트라이에 전화번호를 전부 입력합니다. (insert)

이후에 전화번호부를 하나씩 검색하면됩니다. (search)

검색할 때 end를 만나게되면 다른 전화번호의 접두어이기 때문에 일관성이 없게됩니다.

단, 입력된 전화번호를 그대로 검색에도 사용하기 때문에 같은 전화번호일 경우 이를 무시하시면 됩니다.

 

[구현 코드]

import java.io.*;
import java.util.HashMap;
import java.util.Map;

public class Main {

    private static class CallTrie {
        private class Node {
            Map<Character, Node> child = new HashMap<>();
            boolean end = false;
        }

        private Node root = new Node();

        private void insert(String str) {
            Node parent = root;

            for (int i = 0; i < str.length(); i++) {
                parent = parent.child.computeIfAbsent(str.charAt(i), e -> new Node());
            }
            parent.end = true;
        }

        private boolean search(String str) {
            Node parent = root;
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < str.length(); i++) {
                if (parent == null) return true;

                parent = parent.child.getOrDefault(str.charAt(i), null);
                sb.append(str.charAt(i));
                if (parent != null && parent.end) {
                    if (str.equals(sb.toString())) return true; // 검색된 문자와 같은 단어일 때
                    else return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int testCase = Integer.parseInt(br.readLine());

        StringBuilder answer = new StringBuilder();
        Loop1 : while (testCase-- > 0) {
            int n = Integer.parseInt(br.readLine());

            String[] call = new String[n];
            CallTrie trie = new CallTrie();

            for (int i = 0; i < n; i++) {
                call[i] = br.readLine();
                trie.insert(call[i]);
            }

            for (int i = 0; i < n; i++) {
                boolean result = trie.search(call[i]);

                if (!result) {
                    answer.append("NO").append(System.lineSeparator());
                    continue Loop1;
                }
            }

            answer.append("YES").append(System.lineSeparator());
        }

        bw.write(answer.toString());
        bw.close();
        br.close();
    }
}