BOJ - 5052 전화번호 목록

leehyunjon·2022년 6월 27일

boj 문자열 정렬

Algorithm

목록 보기

82/162

Problem

Solve

전화번호 목록을 이중 for문으로 비교하면 시간초과가 발생할수밖에 없다.
그렇기 때문에 다른 방법을 찾아야한다.

방법은 생각보다 쉬웠다.

정렬을 이용하는 방법인데, 문자열 타입의 숫자를 정렬하게된다면 만약 일관성없는 전화번호로 리스트에 존재한다고 할때 어떤 전화번호의 앞에는 접두어 관계를 가지는 전화번호가 무조건 존재하게 된다.

예를 들어 String[] arr = {113, 12340, 123440, 12345, 98346}을 정렬한다면 {113, 12340, 123440, 12345, 98346}으로 정렬된다.
이는 각 자리수의 숫자를 기준으로 정렬이 되어있는것을 확인할 수 있다.

즉, 어떤 전화번호의 앞에 있는 전화번호만 비교했을 때 일관성 여부를 판단하면 시간초과없이 문제를 해결할 수 있게 된다.

Code

public class 전화번호목록 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int tc = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		while (tc-- > 0) {
			int N = Integer.parseInt(br.readLine());
			String[] numbers = new String[N];

			for (int i = 0; i < N; i++) {
				numbers[i] = br.readLine();
			}
			Arrays.sort(numbers);

			boolean isConsistency = true;
			for(int i=0;i<N-1;i++){
            	//해당 전화번호의 앞의 전화번호와 접두어 관계를 파악하기 위해 startWith()메서드를 사용.
                //접두어 관계라면 해당 전화번호는 일관성없는 전화번호이다.
				if(numbers[i+1].startsWith(numbers[i])) {
					isConsistency = false;
					break;
				}
			}

			if(isConsistency){
				sb.append("YES");
			}else{
				sb.append("NO");
			}
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}