[JAVA] [BOJ] 5052. 전화번호 목록

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

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

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

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

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

 

처음에 이 문제를 보고 TRIE 알고리즘을 떠올렸으나...

 

오늘 더 공부해보면서 약간 느낌만 알았으므로 다른 방법으로 푼 방법을 올리겠습니다.

 

이 문제의 경우 사실 시간만 충분하다면 모든 경우를 다 비교하고 써주면 끝난다.

 

하지만 

 

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

 

라고 써있는 것과 같이 n이 10000까지 이기때문에 단순 for문만 돌더라도 10000 * 10000 = 1억 이 되어 1초가 걸리게 되어 제한 시간인 1초를 넘기게 된다.

 

따라서 최소한으로 비교해야한다는 생각이 들었고

 

그렇다면 최소한으로 하기 위해 앞자리가 같은 경우만 비교하면 어떨까? 라는 생각이 들어 

 

앞자리 순으로 배열을 만들어 사용하였다.

 

Key Point

1. 앞자리 순으로 저장을 해줄 것 

2. 예를 들어 앞자리가 1인 경우가 1만개 들어 올 수 있으므로 1만개 들어오는 경우도 생각을 할 것이다.

( 여담으로 사실 더 좋은 방법이 있지만 최대한 라이브러리를 활용하지 않고 풀기위해 다음과 같은 방법을 썻다는 것을 생각해 주었으면 좋겠다.)

 

-- 추가 설명으로 idxArr 의 경우 어떤 값이 들어온지 모르기 때문에 각 배열의 이제 값을 받을 부분 

    ( 덮어 쓰지 않기 위해 저장하는 배열 )

   arr의 경우 0~9 까지 앞자리를 생각해서 배열을 만들어 써주었다.

   다른 사람의 경우 입력을 받음과 동시에 검사를 하여 두번 돌지 않게 하는 경우도 있었는데 알아서 활용하기 바란다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		int n = 0;
		String[][] arr = null;
		String line = "";
		int[] idxArr = new int[10];
		int firstNum = 0;
		String target = "";
		String compare = "";
		for(int t=1; t<=T; ++t) {
			Arrays.fill(idxArr, 0);
			n = Integer.parseInt(br.readLine());
			arr = new String[10][n];
			
			for(int i=0; i<n; ++i) {
				line = br.readLine();
				firstNum = Integer.parseInt(line.substring(0,1));
				arr[firstNum][idxArr[firstNum]] = line;
				idxArr[firstNum]++;
			}
			String result = "YES";
			printResult:
			for(int i=0; i<10; ++i) {
				for(int j=0; j<idxArr[i]; ++j) {
					target = arr[i][j];
					for(int k=0; k<idxArr[i]; ++k) {
						compare = arr[i][k];
						if(target.length() < compare.length()) {
							if(compare.substring(0, target.length()).equals(target)) {
								result = "NO";
								break printResult;
							}
						}
					}
				}
			}
			bw.write(""+result+"\n");
		}
		bw.close();
		br.close();
	}

}