[Programmers/알고리즘 고득점 KIT] 전화번호 목록

[Programmers] 전화번호 목록

Level 2 | #해시

문제 바로가기 🔗

1. 문제 요약

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제이다.

접두어가 존재하면 False를, 그렇지 않으면 True를 반환한다.

2. 풀이 1: 정렬(Sorting) 활용

def solution(phone_book):
    phone_book.sort() # 문자열 기준 정렬
    for i in range(1, len(phone_book)):
        if phone_book[i].startswith(phone_book[i - 1]):
            return False
    return True

📌 정렬 시 인접 원소만 비교하는 이유: 문자열 정렬은 사전순으로 이루어지므로, 접두사 관계인 번호들은 반드시 서로 붙어서 정렬된다. (예: "119", "1195")

📌 startswith vs in: in은 중간에 포함된 경우도 찾아내지만, startswith는 오직 접두사(시작 부분)만 확인하므로 문제 의도에 정확히 부합한다.

3. 풀이 2: 해시(Hash) 활용

def solution(phone_book):
    hash_map = set(phone_book)
    
    for phone in phone_book:
        for i in range(1, len(phone)):
            if phone[:i] in hash_map:  # O(1) 시간 복잡도 조회
                return False
    
    return True

📌 해시의 핵심: 각 번호를 순회하며 가능한 모든 접두사 슬라이싱(phone[:i]) 결과가 set에 존재하는지 O(1)의 속도로 확인한다.

4. 🆚 두 방식 비교

구분	정렬 방식	해시 방식
시간 복잡도	O(nlog n)	O(nm)
특징	간결하고 직관적임	문제 의도(해시)에 충실함

* n: 전화번호 개수, m: 전화번호의 평균 길이