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

P5052 전화번호 목록 Java

5052번: 전화번호 목록

 

문제

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

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

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

 

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

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

 

입력값

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

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

 

출력값

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

NO
YES

 

알고리즘

이 문제는 전화번호 목록의 일관성 여부를 구해야 한다. 전화번호 목록의 일관성이 유지되려면 하나의 번호가 다른 번호의 접두어인 경우가 없어야 한다.

 

전화번호라는 단어를 문자열이라는 단어로 바꾸어 문제를 다시 해석하겠다. 하나의 문자열이 다른 문자열의 접두어인 경우가 없으면 그 전화번호부는 일관성이 있다고 판단된다.

 

모든 문자열을 저장하고, 임의의 문자열(R)을 모든 문자열과 비교하며 접두어인지 확인하면 된다. 이렇게 문자열을 저장하고 특정 문자열을 탐색하는데 특화된 자료구조가 있다. 바로 트라이이다.

 

그래서 트라이 자료구조를 사용하면 문제가 쉽게 풀린다. 트라이가 무엇인지 모른다면 아래의 글을 미리 읽어보기 바란다.

트라이(Trie) 자료구조

 

위의 블로그 글에서는 트라이의 각 노드에 문자를 저장했다. 이 문제에서는 0~9까지의 숫자만 표현하면 되므로 트라이의 각 노드에 숫자를 저장했다. 숫자로 인덱싱하면 되므로 트라이의 배열을 children으로 이용했다.

static class Trie {
    boolean isEnd;
    Trie children[];

    Trie() {
        isEnd = false;
        children = new Trie[NUM];
        for (int i = 0; i < NUM; i++) {
            children[i] = null;
        }
    }
}

 

다음으로 insert와 search를 구현했다. 우선 모든 전화번호를 트라이에 다 저장한다. 이후에 다시 전화번호 리스트를 처음부터 순회하면서 특정 전화번호가 다른 문자열의 접두어가 되는 경우를 판단하며 반복문을 수행한다. 결과를 StringBuilder로 만들어 출력했다.

 

전체 코드는 다음과 같다.

 

코드

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

public class Main {
    static int TC, N;
    static final int NUM = 10;
    static Trie root;

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

        for (int i = 0; i < TC; i++) {
            N = Integer.parseInt(br.readLine());
            root = new Trie();
            String[] str = new String[N];
            for (int j = 0; j < N; j++) {
                str[j] = br.readLine();
                insert(str[j]);
            }

            boolean answer = true;
            for (int j = 0; j < N; j++) {
                if(!search(str[j])) {
                    answer = false;
                    break;
                }
            }
            if(answer) {
                sb.append("YES\\n");
            } else {
                sb.append("NO\\n");
            }
        }
        System.out.println(sb.toString());
    }

    static void insert(String key) {
        Trie current = root;

        for (int i = 0, size = key.length(); i < size; i++) {
            int target = key.charAt(i) - '0';

            if (current.children[target] == null) {
                current.children[target] = new Trie();
            }
            current = current.children[target];
        }
        current.isEnd = true;
    }

    static boolean search(String key) {
        Trie current = root;

        for (int i = 0, size = key.length(); i < size; i++) {
            int target = key.charAt(i) - '0';
            if (current.isEnd) {
                return false;
            }
            current = current.children[target];
        }
        return true;
    }

    static class Trie {
        boolean isEnd;
        Trie children[];

        Trie() {
            isEnd = false;
            children = new Trie[NUM];
            for (int i = 0; i < NUM; i++) {
                children[i] = null;
            }
        }
    }
}