[BOJ5052/Java] 전화번호 목록

문제 요약

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

5052번: 전화번호 목록

이 문제는 한 번호가 다른 번호의 접두어인 경우가 없는(문제에서는 일관성이 있다고 한다) 전화번호 목록인지를 판단하는 문제이다. 접두어..를 주의깊게 생각해보자..

 

입/출력

입출력에서 단순히 하나의 번호와 다른 모든 번호를 비교해가면서 찾아간다면

50*10000*10000 = 약 50억인가.. 시간초과 날 것이 뻔하므로 뭔가 다른 방법을 찾아야 한다.

 

접근 아이디어

처음에는 접두어니까 맨 앞 숫자가 다르다면 비교를 하지 않는 방법을 생각해보았다.

이를 위해서 정렬을 해주면 index를 차례대로 증가하면서 접근할 수 있지 않을까 생각했는데

그래서 비교할 패턴이 되는 pidx로 접근해서 pidx+1부터 맨 앞 숫자가 같다면 비교를 하는 식으로

접근해보았는데, 계속 틀렸습니다가 떴다.. 시간초과도 아니고 왜 틀렸을까 계속 고민하고 반례도 넣어봤는데

도저히 못찾겠어서 접근 방식이 아예 틀렸나 다시 고민을 해봤다..

 

근데 정렬을 하고 나면... arr[i]에 대해서 arr[i+1]이 아니라면 arr[i]를 접두어로 가질 수 없다..

목록을 정렬했다면 112 다음에는 112보다 큰 전화번호가 오게되는데(1121이라던가, 1122라던가, 1123이라던가)

112 다음에 112를 접두어로 가지지 않는 전화번호 중 가장 작은 번호인 113이 왔다면

1121이나 112를 접두어로 가지는 전화번호는 목록에 없음을 알 수 있다.

따라서 비교시에 굳이 이중포문을 쓰거나 할 필요없이 바로 다음 인덱스만 쓰면 되므로

우리는 O(NlogN)안에(정렬이 있으니까) 모든 테스트케이스를 통과할 수 있다. 코드는 다음과 같다.

작성코드

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

public class Main {

	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++) {
			int N = Integer.parseInt(br.readLine());
			String[] phone = new String[N];
			for(int i= 0; i<N; i++) {
				phone[i] = br.readLine();
			}
			Arrays.sort(phone);
			
			if(listChecker(phone, N))
				sb.append("YES\n");
			else sb.append("NO\n");
//			System.out.println(Arrays.toString(phone));
		}
		
		System.out.println(sb);
	}
	
	static boolean listChecker(String[] arr, int n) {
//		int pidx = 0;
		
		for(int i = 0; i<n-1; i++) {
//			if(pidx == i) continue;
//			if(arr[i].charAt(0) != arr[pidx].charAt(0)) {
//				pidx++;
//				i = pidx+1;
//				if(i >= n) break;
//			}
//			System.out.println(arr[i]+" "+arr[pidx]);
			if(arr[i+1].startsWith(arr[i])) {
				return false;
			}
		}
		return true;
	}
}