[BOJ/JAVA] 백준 5052번 : 전화번호 목록

5052번: 전화번호 목록

 

 

---

 

설명

전화번호 목록이 있다. 해당 목록의 일관성을 확인해라.

전화번호 목록의 일관성은 한 번호가 다른 번호의 접두어이면 안된다는 것이다.

e.g. 119, 11923

 

풀이

해당 문제의 경우 전화번호 수인 N이 최대 10만이기 때문에, O(N^2)의 경우 시간내에 들어오지 못한다. O(NlogN) 방법을 생각했고, 같은 접두어인 경우 인접해있기 때문에 정렬을 사용했다.

 

코드

public class Main {

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);

        int testcase = in.nextInt();
        StringBuilder sb = new StringBuilder();
        while(testcase-->0) {
            int N = in.nextInt();
            String[] numberOfPhone = new String[N];

            for(int i = 0; i < N; i++) {
                numberOfPhone[i] = in.nextLine();
            }

            Arrays.sort(numberOfPhone);

            boolean flag = false;
            for(int i = 1; i < N; i++) {
                if(numberOfPhone[i].startsWith(numberOfPhone[i-1])) {
                    flag = true;
                    break;
                }
            }

            sb.append((flag) ? "NO\n" : "YES\n");
        }

        System.out.println(sb);
    }
}