[프로그래머스] 전화번호 목록 (Hash)

문제 소개

오늘 풀었던 프로그래머스 - 전화번호 목록 문제를 정리합니다.

이 문제는 주어진 전화번호 목록 중 어떤 번호가 다른 번호의 접두어(prefix)인 경우가 있는지를 확인하는 문제입니다.
접두어 관계가 존재하면 false, 존재하지 않으면 true를 반환합니다.

문제 링크: 전화번호 목록 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 전화번호를 사전 순 정렬하면,
   접두어인 경우는 반드시 인접한 위치에 나옴
2. 따라서 인접한 두 번호만 비교해서
   앞 번호가 뒷 번호의 접두어인지 확인하면 충분

---

해결 과정 및 코드

핵심 아이디어

1. 정렬 후 → phone_book[i+1].startsWith(phone_book[i]) 만 확인
2. startsWith()는 문자열 접두어 비교를 빠르게 수행
3. 첫 접두어 발견 즉시 false 반환

코드

시간 복잡도 : O(N log N) (정렬 : O(NlogN) + 인접비교 : O(N))

import java.util.*;

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;
    }
}