백준 5052번: 전화번호 목록(Java, 트리, 트라이)

☑️ 문제

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

✔️관련 알고리즘 개념

트라이

☑️ 문제 분석

• 해당 문제는 트라이 자료구조를 사용하면 된다.
• 우선 일관성이 깨지는 경우는 다음과 같이 두가지이다.

✍️ 첫 번째, 911의 prefix 91이 나중에 나오는 경우

1 // t
2 // n
911
91

• 트라이 자료구조에 911이 있는 상태에서 91을 삽입하는 경우
  • 91에서 1이 삽입되고 isEnd를 true라고 값을 표시한 후
  • 현재 노드에 대해 자식노드가 존재하는지 탐색한다. 만약 자식이 존재하면 일관성이 벗어나는 것이다.
  • 관련 코드

     if(k == phoneNumber.length()-1) {
                            now.isEnd = true;
                            // 자식이 있으면 일관성 위배
                            for (tNode child : now.next) {
                                if (child != null) {
                                    consistency = false;
                                    break;
                                }
                            }
                        }

✍️ 두 번째, prefix 911이 먼저 나오고 9112546이 나중에 나오는 경우

2 // t
3 // n
911
97625999
91125426

• 트라이 자료구조에서 911은 이미 삽입되어 있고 91125426을 삽입하고 있는 경우
  • 91125426에서 세번째 숫자인 1을 삽입했는데 해당 숫자를 다 삽입하지 않았는데도 isEnd가 true인 상태이다. 이 경우는 이미 다른 숫자 값이 존재하여 해당 숫자를 prefix로 갖는 경우이므로 일관성에 벗어나는 것이다.
  • 관련 코드

      if(now.isEnd) {
                            consistency = false;
                            break;
                        }

☑️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int i = 0; i < t; i++) {
            boolean consistency = true;
            int n = Integer.parseInt(br.readLine()); // 전화번호 수

            tNode root = new tNode(); // 루트노드는 공백으로
            for (int j = 0; j < n; j++) {
                String phoneNumber = br.readLine();
                tNode now = root;
                for (int k = 0; k < phoneNumber.length(); k++) {
                    char ch = phoneNumber.charAt(k);
                    if(now.next[ch - '0'] == null) {
                        now.next[ch - '0'] = new tNode();
                    }
                    if(now.isEnd) {
                        consistency = false;
                        break;
                    }
                    now = now.next[ch - '0'];

                    if(k == phoneNumber.length()-1) {
                        now.isEnd = true;
                        // 자식이 있으면 일관성 위배
                        for (tNode child : now.next) {
                            if (child != null) {
                                consistency = false;
                                break;
                            }
                        }
                    }
                }
            }
            System.out.println(consistency ? "YES" : "NO");
        }
    }

    static class tNode {
        tNode[] next = new tNode[10];
        boolean isEnd;
    }
}

☑️ 채점 결과 : 틀림 → 맞음

☑️ 어려웠던 점

• 아래의 경우를 생각하지 못함

1
2
911
91