[백준_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자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

 

[코드]

import java.util.*;

public class BaekJoon_5052 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			int n=sc.nextInt();
			String[] phone_number=new String[n];
			
			for(int i=0;i<n;i++) 
				phone_number[i]=sc.next();
			
			Arrays.sort(phone_number); // 오름차순으로 정렬
			
			// 접두어 관계가 없다면 YES 출력, 없다면 NO 출력
			if(check(n,phone_number))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
	
	// 전화번호 목록이 일관성을 유지하는지 확인하는 함수
	public static boolean check(int n, String[] phone_number) {
		/*
		 * phone_number 배열은 오름차순으로 정렬되어 있는 상태이다. 
		 * 만약 전화번호 목록 내에 접두어 관계가 있는 문자열이 있다면
		 * 배열의 다음 인덱스에 접두어 관계가 있는 문자열이 배치될 것이다. 
		 * 따라서 전화번호 목록이 일관성을 유지하는지 확인하기 위해서는
		 * 특정 문자열과 그 다음 문자열이 접두어 관계를 확인하면 된다. 
		 */
		for(int i=0;i<n-1;i++) {
			if(phone_number[i+1].startsWith(phone_number[i]))
				return false;
		}
		return true;
	}
}

 

[고찰]

 이번 문제는 두 가지를 주의해야 한다. 자바 라이브러리로 제공하는 startsWith() 함수를 사용하는 것과, 해당 함수를 사용할 때 오름차순으로 정렬된 배열을 사용해야 한다는 것이다.

 오름차순으로 정렬된 배열을 사용해야 하는 이유는 만약 전화번호 목록 내에 접두어 관계가 있는 문자열이 있다면 배열의 다음 인덱스에 접두어 관계가 있는 문자열이 배치될 것이다. 따라서 전화번호 목록이 일관성을 유지하는지 확인하기 위해서는 특정 문자열과 그 다음 문자열이 접두어 관계를 확인하면 된다. 

 

<문자열 라이브러리> 비교대상문자열.starsWith("체크할 문자열") : 비교대상 문자열이 체크할 문자열로 시작되는지 여부를 확인하고 true/false 값으로 return 한다. 비교대상문자열.endsWith("체크할 문자열") : 비교대상 문자열이 체크할 문자열로 끝나는지의 여부를 확인하고 true/false 값으로 return 한다.