백준 5052번 - 전화번호 목록

자바의 startsWith()함수를 안다면 비교적 쉽게 풀 수 있는 문제이다.

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

public class Beakjoon5052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < testCase; i++) {
            int t = Integer.parseInt(br.readLine());
            String[] arr = new String[t];
            for (int j = 0; j < t; j++) {
                arr[j] = br.readLine();
            }

            check(arr);
        }
    }

    private static void check(String[] arr) {
        Arrays.sort(arr);

        for (int i = 0; i < arr.length-1; i++) {
            String s1 = arr[i];
            String s2 = arr[i+1];
            if (s2.startsWith(s1)) {
                System.out.println("NO");
                return;
            }

        }
        System.out.println("YES");
    }
}

위 check 함수가 중요한데 만약에 먼저 문제를 보자마자 처음 든 생각은 for문을 두 번 돌려서 완전 탐색으로 푸는 방법이였다. arr[i]를 기준으로 arr[i+1] ~ arr[arr.length-1]까지 보면서 startsWith를 통해 확인하는 것인데 실제로 이렇게 풀면 시간초과가 나온다. 50 * 10000 * 10000을 해보면 1억이 넘어가기에 이러한 방식으로 풀면 안된다. 그러므로 다른 방법으로 풀어야 하는데 위와 같은 방법을 사용하면 더욱 빠르게 풀 수 있다.
위 방법은 모든 값을 탐색하는 것이 아닌 앞 뒤로만 확인하는 방법으로 위 방법을 쓰기 위해서는 먼저 정렬을 해야 한다. 정렬을 하고 나서 앞 뒤로만 체크를 하게 되면 되는데 테스트 케이스의 경우 [911, 91125426, 97625999]로 배열이 들어오게 되는데 먼저 첫번째 값을 통해 뒤 값을 check해보고 통과를 하게 된다면 이동하면 된다.
위와 같은 방법이 왜 통하는지는 정렬을 해보면 알 수 있다.

출처 : 백준 알고리즘 - 전화번호 목록