[백준] G4 5052번 전화번호 목록 (JAVA)

문제 출처 -  Baekjoon Online Judge

문제는 여기

5052번: 전화번호 목록

[문제] 

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

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

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

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

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

[입력]

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

[출력]

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

 

 

---

[풀이]

1. 값을 입력받아 String 배열에 담아준다.

2. 입력받은 값을 정렬해준다. (정렬을 하면 비슷한 것끼리 모임)

3. 정렬이 된 것에서 일관성 검사를 해주고 해당하는 결과를 출력해주면 된다.

[접근]

1. startsWith를 사용해서 일관성 검사를 체크해주었다.

2. 정렬을 하지 않고 처리를 하였었는데 검색을 해보니 정렬을 값이 비슷한 것끼리 모이기 때문에 처리 속도를 단축시킬 수 있다고 하여 해당 방법으로 수정하였다.

[코드]

package BOJ_gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main_G4_5052 {
	static int t;
	static int n;
	static String number[]; // 전화번호
	static boolean consistency; // 일관성

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		
		for (int T = 0; T < t; T++) {
			n = Integer.parseInt(br.readLine());
			number = new String[n];
			consistency = false; // 일관성 체크
			
			for (int i = 0; i < n; i++) {
				number[i] = br.readLine();
			}
			
			// 정렬을 해서 접두어가 비슷한 것끼리 연결이 되도록 해준다.
			Arrays.sort(number);
			
			for (int i = 0; i < n - 1; i++) {
				if (number[i + 1].startsWith(number[i])) { // 접두어라면
					consistency = false; // 일관성 false
					break; // 바로 탈출
				} 
				else // 아니라면 true
					consistency = true;
			}
			
			if (consistency) // 일관성이 있다면
				System.out.println("YES");
			else // 없다면
				System.out.println("NO");
		}
	}
}