[백준 : 골드 4] Java BJ5052 전화번호 목록

 #️⃣문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

 

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

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

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

 

---

#️⃣ 입력

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

 

#️⃣ 출력

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

---

✅ 풀이 Point

1️⃣ Trie 구조 활용

 

    • 왼쪽과 같은 구조로 만들기 위해서 Map 클래스를 사용하여 Key는 Char, Value는 TrieNode인 childNode를 만듬.

 

    • 해당 TrieNode까지 내려왔을 때 완성되는 번호가 있는지 확인하기 위해 terminal이라는 boolean 타입의 변수 선언

static class TrieNode {
    Map<Character, TrieNode> childNode = new HashMap<>();
    boolean terminal; // 종료 노드인지 표기하는 값
}

 

 

    • insert와 해당 char가 trie 노드에 이미 포함되어있는지 확인하는 isContained 함수 작성

public void insert(String word) {
    TrieNode trie = this;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        // childNode에 c없으면 추가
        trie.childNode.putIfAbsent(c, new TrieNode());
        trie = trie.childNode.get(c);
        // 마지막 문자 표시
        if (i == word.length() - 1) {
            trie.terminal = true;
            return;
        }
    }
}

public boolean isContained(String word) {
    TrieNode trie = this;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        TrieNode node = trie.childNode.get(c);

        if (node == null) { // key값이 c라는 childNode가 없다면 해당 단어는 Trie에 포함되지 않음.
            return false;
        }
        trie = node;
    }

    if (trie.terminal && trie.childNode.isEmpty()) { // 해당 노드가 종료 노드이고 자식 노드가 없다면 자기 자신
        return false;
    }
    return true; // 해당 노드가 종료 노드지만 자식이 있다면 해당 번호는 다른 번호에 포함되는 번호
}

 

✅ 정답

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

public class Main {
    static class TrieNode {
        Map<Character, TrieNode> childNode = new HashMap<>();
        boolean terminal; // 종료 노드인지 표기하는 값

        public void insert(String word) {
            TrieNode trie = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                // childNode에 c없으면 추가
                trie.childNode.putIfAbsent(c, new TrieNode());
                trie = trie.childNode.get(c);
                // 마지막 문자 표시
                if (i == word.length() - 1) {
                    trie.terminal = true;
                    return;
                }
            }
        }

        public boolean isContained(String word) {
            TrieNode trie = this;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                TrieNode node = trie.childNode.get(c);

                if (node == null) { // key값이 c라는 childNode가 없다면 해당 단어는 Trie에 포함되지 않음.
                    return false;
                }
                trie = node;
            }

            if (trie.terminal && trie.childNode.isEmpty()) { // 해당 노드가 종료 노드이고 자식 노드가 없다면 자기 자신
                return false;
            }
            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 t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            TrieNode trie = new TrieNode();
            boolean isConsistent = true;

            String[] numbers = new String[N];
            for (int i = 0; i < N; i++) {
                String temp = br.readLine().strip();
                trie.insert(temp);
                numbers[i] = temp;
            }

            for (String number : numbers) {
                if (trie.isContained(number)) {
                    isConsistent = false;
                    break;
                }
            }

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