[Algorithm] 백준 5052 전화번호 목록

[ 문제 ]

전화번호 목록이 주어진다.

이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

 

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

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

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

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다.

전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다.

따라서, 이 목록은 일관성이 없는 목록이다. 

 

[ 입력 ]

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

 

[ 출력 ]

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

 

---

입력으로 주어지는 전화번호들을 PriorityQueue에 넣어줬습니다.

이때 정렬 기준을 재정의해주었는데요.

→ 첫번째 기준 : 사전 순

→ 두번째 기준 : 길이가 짧은 순

 

이렇게 정의하면 큐에서 꺼낸 문자열(s1)이 직후에 꺼낸 문자열(s2)의 접두어인지만 고려해주면 되므로

모든 경우를 고려하지 않아도 되기 때문에 시간초과를 방지할 수 있습니다.

 

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

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 t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine()); // 전화번호 수
			
			PriorityQueue<String> pq = new PriorityQueue<String>(new Comparator<String>() {
				public int compare(String s1, String s2) {
					for(int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
						if(s1.charAt(i) != s2.charAt(i)) return s1.charAt(i)-s2.charAt(i);
					}
					return s1.length()-s2.length();
				}
			});
			
			for(int n = 0; n < N; n++) pq.offer(br.readLine());
			
			boolean flag = false;
			String s1 = pq.poll();
			while(!pq.isEmpty()) {
				String s2 = pq.poll();
				
				if(s1.length()<=s2.length() && s1.equals(s2.substring(0, s1.length()))) {
					flag = true;
					break;
				}
				
				s1 = s2;
			}
			
			if(flag) System.out.println("NO");
			else System.out.println("YES");
		}
	}
}