[백준/Java] 전화번호 목록

 

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

 

전에 풀 땐 문자열 비교해서 풀었는데, 이번에 트라이 써보려고 풀었다.

 

트라이는 문자열 검색을 빠르게 할 수 있는 자료구조이다.

자료가 정수형일 때 이진탐색트리가 O(logN)의 시간복잡도를 가지는데,

문자열일 땐 문자열의 길이가 M이면 O(MlogN) 이다.

이때 트라이를 이용하면 O(M)에 해결할 수 있다.

 

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

public class boj5052 {

    private static class Trie {
        boolean isEnd = false;
        Map<Character, Trie> child = new HashMap<>();

        public void add(String num) {
            Trie trie = this;
            int size = num.length();

            for (int i=0; i<size; i++) {
                char c = num.charAt(i);

                trie.child.putIfAbsent(c, new Trie());
                trie = trie.child.get(c);

                if (i == size - 1) {
                    trie.isEnd = true;
                }
            }
        }

        public boolean contains(String num) {
            Trie trie = this;
            int size = num.length();

            for (int i=0; i<size; i++) {
                char c = num.charAt(i);
                Trie child = trie.child.get(c);

                if (child == null) {
                    return false;
                }

                if (child.isEnd) {
                    return true;
                }

                trie = child;
            }

            return false;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int t=0; t<T; t++) {
            int n = Integer.parseInt(br.readLine());
            Trie trie = new Trie();

            String[] nums = new String[n];
            for (int i=0; i<n; i++) {
                nums[i] = br.readLine();
            }
            Arrays.sort(nums);

            boolean flag = true;

            for (String num : nums) {
                if (trie.contains(num)) {
                    sb.append("NO\n");
                    flag = false;
                    break;
                }
                trie.add(num);
            }

            if (flag) {
                sb.append("YES\n");
            }
        }

        System.out.print(sb);
    }
}

 

 

각 테스트케이스마다 문자열 목록이 들어오면

1. 오름차순 정렬

2. 트라이에 해당 문자열의 부분 문자열이 존재하면 (isEnd = true인 노드 존재) "NO"를 출력하고 멈춘다.

3. 존재하지 않으면 트라이에 해당 문자열을 추가한다.

4. 모든 문자열의 부분 문자열이 존재하지 않으면 "YES"를 출력한다.