[백준 - 5052][Gold 4] - 전화번호 목록 (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를 출력한다.

 

 

문제 해석

---

전화번호가 입력되는데 하나의 전화번호가 다른 전화번호의 접두어가 되지 않는 경우를 찾아야 한다.

 

단순 구현으로 풀릴까?

---

우선 가장 쉬운 방법인 구현을 생각해보자.

 

전화번호를 1개를 고른 후 나머지 모든 전화번호를 하나씩 비교하면 접두어인지 아닌지 판단이 가능하므로 간단한 반복문으로 풀릴 것이다. 이를 수도코드로 표현하면 다음과 같다.

 

for(String 접두어인지 확인하는 전화번호 : 전화번호 목록){
	for(String 나머지 전화번호 : 전화번호 목록){
		for(int 전화번호 인덱스 : 나머지 전화번호 길이){
        
		}
	}
}

위의 수도코드를 기준으로 시간복잡도를 계산해보면 다음과 같다.

 

O(n) = (테스트케이스 수) * (전화번호 고르기) * (나머지 전화번호 고르기) * (전화번호 길이)
= T * N^2 * 10
= 50 * 10,000 * 10,000 * 10
= 50,000,000,000 > 1억

시간복잡도를 계산해보니 단순 구현으로는 최대 연산 횟수가 500억이 나와 제한시간 1초의 연산 횟수인 1억보다 크므로 제한 시간으로는 불가능하다. 다른 방법을 생각해보자.

 

문자열 접두어 알고리즘 = 트라이

---

문자열 알고리즘 중 접두어를 기준으로 하는 문자열 탐색 알고리즘이 있는데 바로 트라이이다. 트라이가 무엇인지 궁금한 분은 아래 링크에 트라이 설명 링크를 달아놓았으니 확인해보면 된다.

https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4

5052번: 전화번호 목록

5052번: 전화번호 목록

트라이

 

 

간단히 요약하자면 트라이는 문자열을 저장할 때 각 글자를 트리로 표현해 저장하는 자료구조이다. 그러므로 같은 접두어를 가지고 있는 단어는 접두어 길이 만큼 같은 노드를 공유한다. 그러므로 특정 단어를 찾을 땐 모든 문자열을 찾지 않고 문자열에 있는 문자를 앞에서부터 따라 가면서 존재하는지 안하는지 따지기 때문에 시간복잡도가 O((문자열의 개수)*(문자열의 개수))에서 O(문자열의 길이)으로 줄게된다!

 

트라이의 구성요소 중 해당 문자열로 끝나는 문자가 있는지 없는지 확인하는 변수가 있다. 그러므로 문자열을 트라이 자료구조에 넣는 과정에 문자열이 끝나는 변수가 참이라면 해당 접두어가 있다는 뜻이므로 접두어가 있는지 없는지 판단할 수 있다.

 

트라이를 이용한 시간복잡도는 다음과 같다.

O(n) = (테스트케이스 수) * (전화번호 개수) * (문자열의 길이)
= T * N * 10
= 50 * 10,000 ** 10
= 5,000,000 < 1억

 

트라이를 이용하면 최대 연산횟수가 5백만으로 제한시간 1초의 연산횟수인 1억보다 작다! 그러므로 트라이를 이용하면 문제를 해결할 수 있다.

 

이때 문자열이 짧은 것이 다른 문자열의 접두어가 될 확률이 문자열이 긴 것보다 놓으므로 문자열의 길이가 짧은 순서로 정렬을 해야한다. 이를 반영한 코드는 다음과 같다.

 

코드

---

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

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

        int T = Integer.parseInt(br.readLine());

        for (int testCase = 0; testCase < T; testCase++) {
            int N = Integer.parseInt(br.readLine());
            Node root = new Node();
            boolean inValid = false;

			//문자열 길이가 짧은 순서로 정렬
            PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.length() - o2.length();
                }
            });

            for (int n = 0; n < N && !inValid; n++) {
                String phoneNumber = br.readLine();
                pq.add(phoneNumber);
            }

			//트라이에 문자열 삽입
            while(!pq.isEmpty()){
                String phoneNumber = pq.poll();
                Node curr = root;

                for (int i = 0; i < phoneNumber.length(); i++) {
                    Node next = curr.next.get(phoneNumber.charAt(i));

                    if (next == null) {
                        next = new Node(phoneNumber.charAt(i));

                        curr.next.put(next.val, next);
                    }
                    //접두어에 해당되는 문자가 있다면 더이상 탐색 X
                    if(next.end){
                        inValid=true;
                        break;
                    }

                    if (i == phoneNumber.length() - 1) {
                        next.end = true;
                    }

                    curr = next;
                }
            }

            if(inValid){
                System.out.println("NO");
            }else{
                System.out.println("YES");
            }
        }
    }
}

class Node{
    char val;
    Map<Character,Node> next = new HashMap<>();
    boolean end;

    public Node(){
    }
    public Node(char val) {
        this.val = val;
    }
}

 

 

실행 결과

---

 

 

제한시간인 1초 안에 문제가 해결되었다!

 

 

키워드

---

• 접두어
  
  • 트라이의 가능성을 가지고 있다.

 

팁

---

문자열 탐색 알고리즘 중 가장 구현하기 쉬운 것은 트라이므로 가장 먼저 생각해보자.