[백준BOJ] 5052번 전화번호 목록.java

 

백준 저지에서 전화번호 목록을 자바를 통해 풀어 보았다. 

 

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

5052번: 전화번호 목록

5052번 전화번호 목록.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1259번 팰린드롬수

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

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

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

설명

처음에는 어렵게 생각했다가 약간 삽질을 했다. 

 

전화번호를 int로 받으면 int의 범위를 넘어간다. 그렇다고 long으로 받게되면 전화번호끼리 비교하기위해 string으로 변환하다거나 이중반복문을 사용하게 되는데 어찌되었든 시간초과로 실패한다. 

 

전화번호를 문자열로 받고 오름차순으로 기본 정렬하게 되면 사전식으로 정렬된다. 예를 들어 12,13,14,123,134라는 전화번호를 받고 정렬하면 12,123,13,134,14 순으로 정렬된다. 이렇게 되면 한 전화번호를 다른 모든 전화번호와 비교할 필요 없이 바로 오른쪽에 있는 전화번호와만 비교하면 된다.

코드

//5052번 전화번호 목록.java
package week4;

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

public class 전화번호_목록_5052 {
	private static int T;
	private static int N;
	private static String[] phoneNumber;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			N = Integer.parseInt(br.readLine());
			phoneNumber = new String[N];
			for(int i=0;i<N;i++) {
				phoneNumber[i] = br.readLine();
			}
			Arrays.sort(phoneNumber);
			
			boolean check=true;
			for(int i=0;i<N-1;i++) {
				if(phoneNumber[i].length()<=phoneNumber[i+1].length()) {
					if(phoneNumber[i].equals(phoneNumber[i+1].substring(0,phoneNumber[i].length()))){
						check=false;
						break;
					}
				}
			}
			if(check)sb.append("YES").append("\n");
			else sb.append("NO").append("\n");
		}
		System.out.println(sb.toString());
	}
}