[정렬] BOJ_5052 전화번호 목록

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

예제 출력 

NO
YES

코드

package sort;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
/**
 * https://www.acmicpc.net/problem/5052
 * 전화번호 목록
 * @author minjung
 *
 */
public class baekjoon_5052 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        sc.init();
        
        int tc = sc.nextInt();
        boolean isOkay[] = new boolean[tc];
        for ( int i = 0; i < tc; i++ ){
            int num = sc.nextInt();
            isOkay[i] = new baekjoon_5052().solve(num);
        }
        
        for ( int i = 0; i < tc; i++ ){
            if(isOkay[i]){
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
 
    private boolean solve(int num) {
        String[] tel = new String[num]; // 전화번호 담을 배열
        
        boolean isConsistency = true;
        for ( int i = 0; i < num; i++ ){ // num만큼 배열에 전화번호를 담는다.
            
            String number = sc.readLine();
            
            if ( number.length() < 11 ){
                tel[i] = number;
            }
            else{
                while ( number.length() > 10 ){
                    System.out.println("10자리 이하 입력해주세요.");
                    number = sc.readLine();
                }
                tel[i] = number;
            }
        }
        Arrays.sort(tel, new Comparator<String>(){ // 길이가 짧은 순서로 정렬
 
            @Override
            public int compare(String o1, String o2) {
                return Integer.compare(o1.length(), o2.length());
            }
        });
        
        for ( int i = 0; i < tel.length/2; i++ ){ //기준
            for (int j = i+1; j < tel.length; j++ ){ // 비교대상
                if ( tel[j].substring(0, tel[i].length()).equals(tel[i]) ){
                    isConsistency = false;
                    break;
                }
                else {
                    isConsistency = true;
                }
            }
            if( !isConsistency ){
                break;
            }
        }
        return isConsistency;
    }
 
    static class sc { 
        private static BufferedReader br;
        private static StringTokenizer st;
        
        static void init() {
            br = new BufferedReader(new InputStreamReader(System.in));
            st = new StringTokenizer("");
        }
 
        static String readLine() {
            try{
                return br.readLine();
            } catch (IOException e){
                e.printStackTrace();
            }
            return null;
        }
        
        static String next() {
            while (!st.hasMoreTokens() ){
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        static long nextLong() {
            return Long.parseLong(next());
        }
        
        static int nextInt() {
            return Integer.parseInt(next());
        }
        
        static double nextDouble() {
            return Double.parseDouble(next());
        }
        
    }
 
}