[Algorithm: 해시] 프로그래머스 <전화번호 목록 >

Hash Java Programmers Lv.2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=java

프로그래머스

 

문제 설명

전화번호부 목록이 주어질 때, 한 번호가 다른 번호의 접두사(prefix)인 경우가 있으면 false, 없으면 true를 반환하는 문제다.

예를 들어 ["119", "97674223", "1195524421"]가 주어지면,
"119"가 "1195524421"의 접두사이므로 false를 반환해야 한다.

 

---

 

처음 접근: 이중 for문

모든 번호 쌍을 비교하면 되지 않을까? startsWith()를 이용해 모든 조합을 순회하는 방식으로 접근했다.

 

❌ 처음 코드 — 정답은 맞지만 성능 이슈

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book.length; j++) {
                if (phone_book[i].startsWith(phone_book[j]) && i != j) {
                    answer = false;
                }
            }
        }

        return answer;
    }
}

 

 

정답 자체는 맞다. 하지만 배열의 길이가 n이라면 최악의 경우 n × n번 비교가 발생한다.

이 문제의 제한사항은 전화번호 최대 1,000,000개다.
이중 for문은 O(n²) - 최대 1조 번 비교가 발생해 시간 초과가 난다.

n (번호 개수)	O(n²) 연산 횟수	결과
1,000	1,000,000	통과
100,000	10,000,000,000	시간 초과
1,000,000	1,000,000,000,000	시간 초과

 

 

핵심 아이디어: 정렬 후 인접 비교

어떻게 하면 모든 쌍을 비교하지 않아도 될까?

핵심 관찰은 다음과 같다.

접두사 관계는 정렬하면 반드시 인접하게 붙는다.
사전순 정렬을 하면 접두사인 번호는 그것으로 시작하는 번호 바로 앞에 위치하기 때문에,
이웃한 두 원소만 비교하면 충분하다.

정렬 전 vs 정렬 후 비교

정렬 전 1195524421 97674223 119

정렬 후 119 1195524421 97674223

인접 비교 119 → "1195524421".startsWith("119") ✓

접두사 발견 → false

접두사 없는 경우 — ["123", "456", "789"]

정렬 후 123 456 789

인접 비교 123→456 ✗ 456→789 ✗

접두사 없음 → true

 

왜 인접 비교만으로 충분한가?

사전순 정렬을 하면 문자열은 공통 앞부분이 같을수록 가까이 붙는다.

1

"119"는 "1195..."보다 사전순으로 항상 앞에 온다.

2

즉, A가 B의 접두사라면 정렬 후 A와 B는 반드시 인접한다.

3

따라서 이웃한 [i]와 [i+1]만 비교하면 모든 접두사 쌍을 잡아낼 수 있다.

 

 

 

최종 코드

 

✅ 개선 코드 — O(n log n)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);    // 사전순 정렬 — O(n log n)

        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;           // 인접 원소만 비교 — O(n)
            }
        }

        return true;
    }
}

전체 시간복잡도: O(n log n) (정렬) + O(n) (순회) = O(n log n)
이중 for문 O(n²) 대비 n = 1,000,000 기준으로 약 50,000배 빠르다.

 

---

 

 

정리

O(n²) → O(n log n)

정렬 하나로 이중 for문을 단일 순회로 줄임

정렬의 힘

사전순 정렬 후 접두사 관계는 반드시 인접하게 위치함

인접 비교

정렬된 배열에서 [i]와 [i+1]만 비교하면 충분

정답이 맞더라도 시간복잡도를 항상 의식해야 한다.
이중 for문이 보이면 "정렬 후 단일 순회로 바꿀 수 없을까?"를 먼저 떠올리자.

 

 

 

 

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.