문제
전화번호 목록이 일관성 있는지 확인하는 문제이다. 한 번호가 다른 번호의 접두사(prefix)인 경우 일관성이 없다고 판단한다.
예를 들어, 긴급전화 911이 목록에 있고 91125396도 있다면, 911로 시작하므로 긴급전화에 전화하려 할 때 자동으로 연결되지 않는다.
입력
첫째 줄에 테스트 케이스의 개수 t(1 ≤ t ≤ 50)가 주어진다. 각 테스트 케이스의 첫째 줄에 전화번호의 개수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 n줄에 전화번호가 하나씩 주어진다. 전화번호의 길이는 10을 넘지 않는다.
출력
각 테스트 케이스마다 목록이 일관성 있으면 YES, 없으면 NO를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 3 emergency 911 alice 97625999 bob 91125426 5 emergency 911 alice 97625999 bob 91125426 carol 593 dave 64112960 | NO YES |
풀이
전화번호 목록을 사전순(lexicographic) 정렬 후, 인접한 번호들 사이의 접두사 관계만 검사하는 방식으로 풀이한다.
- 각 테스트 케이스의 전화번호 배열을
Arrays.sort()로 사전순 정렬한다. - 사전순 정렬 시 접두사 관계인 번호는 반드시 인접하게 위치하므로,
phn[i].startsWith(phn[i-1])만 확인하면 된다. - 인접한 번호 쌍에서 앞 번호가 뒤 번호의 접두사이면
NO, 그렇지 않으면YES를 출력한다.
핵심 아이디어: 사전순 정렬을 하면 한 번호가 다른 번호의 접두사일 때 두 번호가 반드시 인접한다. 따라서 전체 쌍(N^2)을 비교하지 않고 인접 쌍(N)만 확인하면 O(N log N)에 풀 수 있다. 트라이(Trie)로도 풀 수 있으나 정렬이 더 간결하다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Day137BOJ5052전화번호목록 {
static int N;
static String[] phn;
static boolean ans;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
N = Integer.parseInt(br.readLine());
phn = new String[N];
ans = true;
for (int i = 0; i < N; i++)
phn[i] = br.readLine();
Arrays.sort(phn);
for (int i = 1; i < N; i++)
if (phn[i].startsWith(phn[i - 1])) {
ans = false;
break;
}
sb.append(ans ? "YES" : "NO").append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)