owel의 블로그

프로그래머스 문제 풀이 - 전화번호 목록 (Java)

문제 링크

프로그래머스 - 전화번호 목록

풀이 아이디어

전화번호 목록에서 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 반환하는 문제입니다.

완전탐색으로 모든 쌍을 비교하면 시간복잡도가 O(n²)이므로, 원소 개수가 최대 100만 개인 이 문제의 조건에서는 시간 초과가 발생합니다.

이를 해결하기 위해 사전순 정렬을 활용합니다.
번호 문자열을 사전순으로 정렬하면, 인접한 두 문자열 A, B (A가 앞)에 대해 다음 두 가지 성질이 성립합니다.

1. B→A 방향의 검사가 필요 없습니다:
사전순에서 B는 A보다 뒤에 있으므로, B가 A의 접두어가 되는 경우는 존재하지 않습니다. 따라서 A가 B의 접두어인지만 검사하면 됩니다.

2. 인접한 쌍만 검사하면 충분합니다:
사전순으로 정렬하면 같은 접두어를 가진 문자열끼리 항상 나란히 붙으므로
앞에서부터 인접한 두 개씩 차례로 비교하는 과정 한 번으로 모든 접두어 관계를 검사할 수 있습니다.

위 두 성질 덕분에 검사 단계의 시간복잡도가 O(n²)에서 O(n)으로 줄어듭니다.
총 시간복잡도는 정렬 O(n log n) + 검사 O(n)이므로
O(n log n)의 시간복잡도로 문제를 해결할 수 있습니다. (최악의 경우 약 2,000만 번)

정답 코드

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }
}