[트리#5] 백준 5052번: 전화번호 목록 JAVA

5052번: 전화번호 목록

문제

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

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

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

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

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

 

 

입력

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

 

 

출력

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

 

 

예제입출력

 

 

풀이

이번 문제는 알고리즘 분류로 트리로 되어있는데, 굳이 트리를 이용해서 풀어야하는지는 의문이다. 트리로 접근하는 것보단 그냥 String클래스의 startsWith()함수를 이용하여 해당 전화번호가 다른 전화번호의 접두어로 존재하는지 여부를 체크하면 쉽게 풀릴거라고 생각했다.

 

여기서, String 클래스의 startsWith()함수는 해당 문자열이 특정 문자열로 시작하는지 여부를 체크해서 boolean값으로 반환해주는 함수이다. ex) "abc".startsWith("abc")    //true를 반환.

 

그래서 나는 startsWith()함수를 이용하였고 그냥 간단하게 시간복잡도가 O(N^2)으로 전화번호부를 돌면서 해당 문자열이 전화번호부내에 존재하는 모든 문자열에 대하여 서로 접두어 관계인지 확인했다. 뭔가 시간초과 판정을 받을 것 같았는데 역시나 시간 초과 판정을 받았다. 따라서 더 개선된 방법이 필요했다.

 

바로 정렬과 접두어 관계의  특징을 이용하는 것이다. 전화번호부 배열을 정렬을 해놓고 보면, 특정 문자열이 서로 접두어 관계를 가지는 상황은 n, n+1과 같은 필연적으로 서로 붙어있는 상황이다. ex) "122", "123", "1234"

 

따라서 알고리즘을 특정 문자열과 그 다음 문자열에 대하여 startsWith() 메소드를 이용하여 접두어 관계인지 체크해주면 된다. 시간복잡도도 O(N)으로 개선된다.

 

 

소스코드

import java.io.*;
import java.util.Arrays;

public class Tree5_5052 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        boolean check;

        for (int i = 0; i < t; i++) {
            check = false;
            int n = Integer.parseInt(br.readLine());

            String[] numbers = new String[n];
            for (int j = 0; j < n; j++) {
                numbers[j] = br.readLine();
            }

            Arrays.sort(numbers);

            for (int k = 0; k < numbers.length-1; k++) {
                if (numbers[k+1].startsWith(numbers[k])) {
                    bw.write("NO\n");
                    check = true;
                    break;
                }
            }
            if (!check) {
                bw.write("YES\n");
            }

        }
        bw.flush();
        bw.close();
        br.close();
    }
}