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

문제내용

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

5052번: 전화번호 목록

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

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

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

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

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

입력

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

출력

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

---

문제풀이

이번 문제는 구현자체는 매우 쉽지만 방법을 떠올리기 쉽지 않았다. 이전에 프로그래머스에서 비슷한 문제를 본거 같은데 기억이 가물가물하기도 하고...ㅋㅋㅋ

여튼 처음엔 O(N^2)으로 풀었으나 이렇게 풀어버리면 테케 포함 최악의 경우 5,000,000,000 연산을 해야하기 때문에 1초안에는 절대로 통과할수 없다.

그래서 다음과 같은 방법으로 푼다.

 

1. 문자열로 전화번호를 배열에 받고 오름차순 정렬하기.

2. 배열을 0~n-1번째 까지 탐색하면서 다음 요소값이 현재 요소값으로 시작하는지 검사.

3. 2번 검사에서 현재 요소값으로 시작하는게 맞으면 NO , 아니면 YES를 출력

 

3개의 과정이면 충분하다. 이과정을 좀 풀어서 설명해보면 아래와 같다.

1번에서 오름차순 정렬만 해줘도 되는 이유는 문제의 조건 덕분이다. 문제에선 접두어라는 힌트를 줬다.

따라서 오름차순 정렬을 하게 됐을때 만약 접두어가 있다면 그 문자열을 붙어 있을수 밖에 없다.

예를들어

{ 123 , 3829, 7, 12359, 1245 } 라는 배열이 있을때 정렬하게되면

{ 123, 12359, 1245, 3829, 7 } 로 오름차순 정렬된다.

여기서 접두어가 있는 전화번호 목록은 반드시 붙어있을수 밖에 없다는걸 이해하면된다.

 

2번에서 요소값을 검사하는건 startWith를 활용한다. (어차피 접두어만 보면되기 때문에)

따라서 (다음요소값).startWith(현재요소값) 으로 확인해주면된다.

 

3번에선 2번의 과정이 true로 나오게 되면 NO를 출력해주면 된다. 그외엔 모두 YES출력.

 

코드를 보자.

 

---

코드

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

public class Main {
	static int t,n;
	static String[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(t-->0) {
			n = Integer.parseInt(br.readLine());
			arr = new String[n];
			for(int i=0; i<n; i++)
				arr[i] = br.readLine();
			
			Arrays.sort(arr);//오름차순 정렬
			
			boolean flag = false;//접두어가 있으면 true, 없으면 false
			for(int i=0; i<n-1; i++) {
				if(arr[i+1].startsWith(arr[i])) {//접두어가 있는지 검사
					flag=true;
					continue;
				}
			}
			
			if(flag) sb.append("NO").append("\n"); //접두어 x
			else sb.append("YES").append("\n"); //접두어 o
		}//while
		
		System.out.println(sb.toString());
	}
}

 

 

프로그래머스랑 같은 로직으로 풀이.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Iterator;

public class Main {
	static int t,n;
	static String[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		while(t-->0) {
			n = Integer.parseInt(br.readLine());
			HashSet<String> set = new HashSet<String>();
			for(int i=0; i<n; i++) {
				String str = br.readLine();
				set.add(str);
			}
			
			boolean flag = false;
			Iterator<String> iter = set.iterator();
			while(iter.hasNext()) {
				String key = iter.next();
				for(int i=0; i<key.length(); i++) {
					if(set.contains(key.substring(0, i))) {
						flag = true;
						break;
					}
				}
				if(flag) break;
			}
			
			if(flag) sb.append("NO").append("\n");
			else sb.append("YES").append("\n");
		}//while
		
		System.out.println(sb.toString());
	}
}

---

마치며

말했다시피 구현은 쉬우나 완전탐색 없이 어떻게 시간을 줄여하는지 고민을 해봐야 했던 문제고, 그래서 그런지 생각보다 시간이 오래걸린 문제다. 그리고 시간은 비슷하지만 메모리측면에선 백준의 풀이가 더 좋다.