[알고리즘 문제풀이] 백준 5052 전화번호 목록

오늘 푼 문제는 백준 5052 전화번호 목록이다. 나는 트라이로 이 문제를 풀었고, 풀면서 겸사겸사 트라이를 정리 및 구현을 해보았다. 이 내용은 여기서 확인할 수 있다 !

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

예제

입력 1

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

출력 1

NO
YES

풀이 방법

트라이를 이용해서 문제를 해결했다. 따라서 먼저 필요한 정도의 범위까지 트라이를 구현하였다. ( 자바로 트라이 구현하는 것이 궁금하거나 아래 코드에 구현된 트라이에 대해서 궁금하면 이 글의 맨 위에 링크 걸어둔 트라이 글을 참고하면 된다! )

이 문제에서는 insert만이 필요하기 때문에 insert를 구현하였고, 문제의 요구대로 번호가 다른 번호의 접두어가 되는 경우에는 false를 반환하도록 해주었다. 여기서 다른 번호의 접두어인지 판단하는 기준은 아래의 두 개와 같다.

1. 트라이에 번호를 넣는 중이고, 마지막 숫자가 아닌데, 해당 숫자가 어떤 숫자의 마지막 숫자인 경우
   • 이 경우는 이미 들어있는 어떤 번호가 현재 넣고있는 번호의 접두어인 것이다.
2. 트라이에 번호를 다 넣었을 때, 마지막 숫자의 노드가 다른 자식을 더 가지고있는 경우
   • 이 경우는 지금 넣는 번호가 이미 들어있는 어떤 번호의 접두어인 것이다.

테스트 케이스의 수와 각 테스트 케이스에 포함된 번호 수에 맞게 입력 값을 잘 받으면서, 숫자를 insert 해주고 하나도 false를 반환한다면 해당 결과는 NO가 되는 것이다. 그렇지 않고 다 true를 반환하면 결과는 YES가 되는 것이다 !

코드

package com.gowoon;

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

public class Main {
    public static class Node{
        private Map<Character, Node> childNodes = new HashMap<>();
        private boolean isLast;
    }

    public static class Trie{
        private Node root;
        Trie(){
            this.root = new Node();
        }
        boolean insert(String number){
            Node node = this.root;
            for(int i=0; i<number.length(); i++){
                node = node.childNodes.computeIfAbsent(number.charAt(i), c -> new Node()); 
                if(node.isLast && i<number.length()-1) return false; 
            }
            if(!node.childNodes.isEmpty()) return false; 
            node.isLast = true;
            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 t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++){
            int n = Integer.parseInt(br.readLine());
            boolean flag = true;
            Trie trie = new Trie();
            for(int j=0; j<n; j++){
                String number = br.readLine();
                if(flag){
                    if(!trie.insert(number)) flag = false;
                }
            }
            if(flag) bw.write("YES\n");
            else bw.write("NO\n");
            bw.flush();
        }

        bw.flush();
        bw.close();
        br.close();
    }
}