[백준/5052번] 전화번호 목록(NCPC 2007)[Java]

 

 

문제

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

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

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

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

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

입력

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

출력

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

 

---

풀이

 버퍼로 입력값을 받아주고 Comparator를 통해서 사전순으로 정렬해준다. 이후 핵심인 starrsWith()함수를 이용해서 이중포문을 사용할 필요없이(사용하면 시간초과 발생) 이전과 비교해주면서 진행해주면 정답을 구할 수 있다.ㅇㅅㅇ

 

import java.util.*;
import java.io.*;
 
//시간줄이기????????????
 
public class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); //문자스트림
        int n = Integer.parseInt(br.readLine()); //testcase개수
        
        for(int i=0;i<n;i++) {
            int t = Integer.parseInt(br.readLine()); //개수 전화번호
            String  [] arr= new String[t];
            int sw=0; //yes,no 판별기준 스위치            
            for(int j=0;j<t;j++) {
                arr[j]=br.readLine();
            }//배열완성 
            //정렬과 스위치 구현
            Arrays.sort(arr, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.compareTo(o2);                    
                }
            }); //사전순으로 정렬
            
            for(int j=1;j<t;j++) {
                if(arr[j].startsWith(arr[j-1])) {
                    sw=1;
                    break;
                }
            }
            System.out.println(sw==0?"YES":"NO");
        }
    }
}
 

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

5052번: 전화번호 목록