백준 5052번 : 전화번호 목록(Java)

---

[풀이]

• java의 startsWith() 메소드를 이용하면 풀 수 있습니다.
• 하지만, startsWith() 메소드를 사용하기 이전에 정렬을 하면 시간 복잡도를 줄일 수 있습니다.
• 정렬을 하지 않을 경우 O^2의 시간복잡도로 모든 경우를 다 탐색해야하지만, 정렬을 할 경우에는 바로 앞, 뒤 배열의 값만 비교하면 되므로 시간초과가 나지 않습니다.
• 프로그래머스의 전화번호 목록 문제와 거의 비슷한 문제입니다.

---

[코드]

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        String[] arr;
        boolean flag;
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            arr = new String[n];
            flag = true;

            for (int i = 0; i < n; i++) {
                arr[i] = br.readLine();
            }

            Arrays.sort(arr);

            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i + 1].startsWith(arr[i])) {
                    flag = false;
                }
            }

            if (flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}