[백준] 전화번호 목록 - 자바(Java)

문제 링크

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

문제 설명

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

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

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

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

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

입력

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

출력

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

입출력 예

입력	출력
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346	NO YES

 

문제 풀이

[고려사항]

전화번호수는 최대 10,000(만)개라서 만약 시간 복잡도가 O(N^2)이 되면 100,000,000(1억) 인데 제한시간이 1초라서, 모든 문자를 돌면서 찾는게 아닌 방법을 찾아야한다.

[알고리즘, 구현방법]

문제에서 전화번호 길이가 길어야 10자리라고 했고, 문자열에 대한 검색을 빠르게 처리해야하기 때문에 트라이(Trie)를 사용해서 구현했다.

트라이는 문자열 추가와 탐색을 O(M)만에 가능하게 하기 때문에 이 문제에 적합하다고 생각했다. (+메모리 크기가 단점이지만, 이 문제에서는 전화번호 길이가 길어야 10자리)

*트라이 관련 포스팅은 아래에서 참고

[자료구조] 트라이(Trie)

✅ 정답

입력으로 받은 전화번호 길이가 짧은 순으로 트라이에 문자를 추가하면서, 해당 문자의 자식노드가 있고, 그 자식 노드가 단어의 끝이라면 일관성이 없는 경우에 해당한다.

 

이때 전화번호 길이가 짧은 순으로 하지 않고 길이가 긴 문자열부터 추가하면서 확인한다면, 위의 조건으로는 제대로 검증할 수 없다. 만약 911234이 먼저 트라이에 추가되고 911이 들어온다면, 911234가 추가는 되어있지만, 911에서 마지막 1에 단어의 마지막이라는 표시가 없기 때문에 위의 조건에 부합하지 않는다.

 

그래서 전화번호를 먼저 모두 입력받아서 저장하고, 전화번호의 길이가 짧은 순으로 정렬해서 트라이에 전화번호를 추가하면서 확인하였다.

[풀이 과정]

1. 테스트 케이스별로 전화번호를 입력받아 배열에 저장한 후 전화번호 길이가 짧은 순으로 정렬
2. Trie 생성하면서 일관성 여부 판단
   • Trie 생성시, 문자열에 대해 문자(Character)하나씩 노드를 생성하면서 자식 노드를 생성하는데,
     • 이때, 현재 탐색중인 문자(노드)의 자식 노드로 이미 해당 문자가 있고, 그 문자의 endOfWord가 true(=단어의 끝)이면 일관성 없는 목록으로 판단
     • 예시) 911에 대해 이미 "9"→"1"→"1"(endOfWord) 로 생성되어있는 상태에서, 911234에 대해 Trie 생성을 하면 "9"→"1"→"1"에서 마지막 "1"에 endOfWord가 true이므로 일관성이 없다고 판단
3. 테스트 케이스별로 일관성 여부 결과를 담은 배열을 순회하면서 true인 경우 YES, false인 경우 NO를 출력

정답 코드

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

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

        int t = Integer.parseInt(st.nextToken());

        boolean[] answers = new boolean[t];
        for (int i=0; i<t; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            // 한번에 다 받은 후에 길이가 짧은 순으로 정렬
            String[] numbers = new String[n];
            for (int j=0; j<n; j++) {
                st = new StringTokenizer(br.readLine());
                numbers[j] = st.nextToken();
            }
            Arrays.sort(numbers, (o1, o2) -> o1.length() - o2.length());

            // Trie 생성
            // Leaf 노드가 아닌데 endOfWord가 되면, 일관성 없는 목록
            Trie trie = new Trie();
            boolean flag = true;
            for (String number: numbers) {
                // 일관성 없는 목록으로 판단되면 해당 테스트 케이스 반복 종료
                if (flag) flag = trie.insert(number);
            }
            answers[i] = flag;
        }
        // 결과 출력
        for (boolean answer: answers) {
            if (answer) System.out.println("YES");
            else System.out.println("NO");
        }
    }
    public static class Node {
        public HashMap<Character, Node> childNode = new HashMap<>(); // 자식 노드
        public boolean endOfWord = false;
    }
    public static class Trie {
        private Node rootNode;
        public Trie() {
        	rootNode = new Node();
        }
        public boolean insert(String number) {
            Node node = this.rootNode;
            
            for (int i=0; i<number.length(); i++) {
                // 자식 노드에 문자가 있고, 그 자식 노드가 단어의 끝(endOfWord)이면 일관성 없음
                if (node.childNode.containsKey(number.charAt(i))
                    && node.childNode.get(number.charAt(i)).endOfWord) {
                    return false;
                }

                // 자식 노드에 있는 문자라면 자식 노드를 가져오고, 자식 노드에 없다면 새로 생성
                // computeIfAbsent: Map에 Key가 없다면 Value를 새로 만들어줌
                node = node.childNode.computeIfAbsent(number.charAt(i), key -> new Node());
            }
            node.endOfWord = true; // 번호의 문자를 모두 순회하면 마지막 노드는 리프 노드
            return true;
        }
    }
}