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

BOJ Link

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

 

풀이 과정

정렬 + 트리(트라이) 문제다.

 

일반적인 구현이라면 길이를 기준으로 내림차순 정렬하고, insert 동작 이후 마지막 노드가 리프노드가 아닐 시 No임을 체크할 수 있다. (이는 문제에서 일관성이 없는 전화번호 목록이라고 표현한다.)

 

나는 정렬을 사용하지 않았다. 그러려면, 다음과 같은 케이스를 고려해야 한다.

 

12

123

 

이는 insert시 12의 경우 마지막 수가 리프 노드(123의 insert를 수행하기 전 이므로) 이며

123의 경우 또한, 마지막 수가 리프 노드가 된다.

 

그러므로 이를 고려하여, 123의 insert 도중 노드가 이미 존재했고, 리프 노드라면(isEnd, 위의 경우 2번 노드)

No 로 체크한다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class Main {

    static class Node {

        boolean isEnd;
        Map<Character, Node> child = new HashMap<>();
    }

    static boolean insertAndFind(Node node, String num) {

        Node cur = node;
        for (int i = 0; i < num.length(); i++) {

            // 현재 탐색의 마지막 노드가 원래 trie에 있던 노드인 경우 -> 다른 단어의 접두사가 된다.
            if (i == num.length() - 1 && cur.child.get(num.charAt(i)) != null) return false;

            cur = cur.child.computeIfAbsent(num.charAt(i), cn -> new Node());

            // 이미 trie에 노드가 있었고, 리프 노드였다면 -> 기존 단어가 현재 탐색의 접두사가 된다.
            if (cur.isEnd) return false;
        }

        cur.isEnd = true;
        return true;
    }

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

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

        for (int tc = 0; tc < T; tc++) {
            int N = Integer.parseInt(br.readLine());

            Node root = new Node();
            boolean isAns = true;

            for (int i = 0; i < N; i++) {
                if (!insertAndFind(root, br.readLine())) {
                    isAns = false;

                    // 불 필요한 탐색 제거
                    while (N - i - 1 > 0) {
                        br.readLine();
                        i++;
                    }
                    break;
                }
            }

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