[백준] 5052번: 전화번호 목록

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

5052번: 전화번호 목록

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(bf.readLine());	// 테스트 케이스 수
		for(int tc=0; tc<t; tc++) {
			int n = Integer.parseInt(bf.readLine());	// 전화번호 수
			String[] phones = new String[n];	// 전화번호 목록
			String result = "YES";	// 결과 출력
			
			for(int i=0; i<n; i++) 
				phones[i] = bf.readLine();
			
			Arrays.sort(phones);
			for(int i=0; i<n-1; i++) {
				// 한 번호가 다른 번호의 접두어 인 경우
				if(phones[i+1].startsWith(phones[i])) {
					result = "NO";
					break;
				}
			}
			System.out.println(result);
		}
		bf.close();
	}

}

풀이

기존 프로그래머스와 동일한 문제다.

 

프로그래머스 - 전화번호 목록

 

하지만 프로그래머스에서 풀었던 코드처럼 모든 전화번호 목록에 대해 완전 탐색 O(n^2) 으로 해결하면, 시간초과가 발생하는데, 이 문제에서는 테스트케이스가 포함되기 때문이다.

테스트케이스는 50, 전화번호 수는 10,000 이므로 O(50*10000*10000) 으로 시간 초과가 발생한다.

그럼 시간 초과를 해결해야 하는데, 이 문제는 정렬을 통해 해결할 수 있다.

전화번호가 123, 12, 1234 라면 정렬을 하면 12, 123, 1234 와 같이 된다.

그럼 모든 전화번호를 검사할 필요없이 이전의 번호와 접두어 관계인지만 파악하면 된다.

또한 전화번호 목록에, 하나라도 접두어 관계가 있는 번호라면, 다른 전화번호는 확인할 필요가 없다.

따라서 접두어를 확인했을 경우, break를 통해 탈출함으로써 시간을 좀 더 줄일 수 있다.

 

 

* 이 문제는 트라이(Trie) 자료구조의 문제라고 한다. 트라이는 문자열에서의 검색을 빠르게 해주는 자료구조 이다.

트라이 자료구조란 ?

https://jason9319.tistory.com/129

[자료구조]트라이(Trie)