1 문제 정보

제목: 전화번호 목록
링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577
난이도: 2
유형: Hash
풀이 시간: 10분

2 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

2.1 제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다.

2.2 입출력 예제

예시	phone_book	return
예시 1	[“119”, “97674223”, “1195524421”]	false
예시 2	[“123”,“456”,“789”]	true
예시 3	[“12”,“123”,“1235”,“567”,“88”]	false

2.3 입출력 예 설명

입출력 예 #1 앞에서 설명한 예와 같습니다.

입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

2.4 알림

2021년 3월 4일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

3 문제 해설

3.1 문제 핵심 이해

이 문제의 핵심은 한 전화번호가 다른 전화번호의 접두어인지 확인하는 것

입력: 전화번호 목록 배열
출력: 접두어 관계가 있으면 false, 없으면 true
목표: 효율적으로 접두어 관계 탐지

3.2 중요한 조건들

접두어 정의: 한 번호가 다른 번호의 시작 부분과 완전히 일치
대용량 데이터: 최대 1,000,000개의 전화번호 처리 필요
효율성 요구: O(n²) 방식으로는 시간 초과 발생 가능

3.3 해결 방법별 분석

3.3.1 알고리즘 요약

3.3.1.1 핵심 아이디어

사전순 정렬 후 인접한 번호끼리만 비교하여 O(n log n) 시간에 모든 접두어 관계를 효율적으로 탐지

3.3.1.2 알고리즘 동작

사전순 정렬: 전화번호를 문자열 기준으로 정렬
인접 비교: 정렬된 배열에서 인접한 두 번호만 접두어 관계를 확인
조기 종료: 접두어 관계를 발견하면 즉시 false를 반환

3.3.1.3 왜 효율적인가?

정렬의 특성상 접두어 관계가 있다면 반드시 인접한 위치에 배치되므로, 모든 쌍을 비교할 필요가 없음

3.3.1.4 핵심 포인트

“정렬된 상태에서 접두어는 반드시 인접하다”는 특성을 활용하여 O(n²) → O(n log n)로 시간복잡도를 획기적으로 개선

3.3.2 정렬 방법 (권장)

시간복잡도: O(n log n)
공간복잡도: O(log n)

def solution(phone_book):
    # 사전순 정렬 - O(n log n) 시간, O(log n) 공간(정렬 알고리즘 스택)
    phone_book.sort()
    
    # 인접한 번호끼리만 접두어 관계 확인 - O(n) 시간, O(1) 공간
    for i in range(len(phone_book) - 1):  # O(n) 반복
        # startswith 비교 - O(m) 시간 (m: 짧은 번호의 길이)
        if phone_book[i+1].startswith(phone_book[i]):
            return False  # O(1) 시간, O(1) 공간
    
    return True  # O(1) 시간, O(1) 공간

# 전체 시간복잡도: O(n log n) + O(n * m) = O(n log n) (m << log n 일반적)
# 전체 공간복잡도: O(log n) (정렬 알고리즘의 스택 공간)

동작 원리: - 사전순 정렬 후 인접한 번호끼리만 비교 - 정렬되어 있으면 접두어 관계는 반드시 인접한 위치에 존재 - 예: [“119”, “1195524421”, “97674223”] 정렬 시 “119”와 “1195524421”이 인접

3.3.3 해시셋(Set) 방법

시간복잡도: O(n×m²) (n: 번호 개수, m: 평균 번호 길이)
공간복잡도: O(n×m)

def solution(phone_book):
    # 모든 번호를 해시셋에 저장 - O(n) 시간, O(n * m) 공간
    phone_set = set(phone_book)  # n개 번호, 각 번호 평균 m자리
    
    # 각 번호의 모든 접두어가 해시셋에 있는지 확인 - O(n * m) 시간
    for phone in phone_book:  # O(n) 반복
        for i in range(1, len(phone)):  # O(m) 반복 (m: 전화번호 길이)
            # 슬라이싱 O(i), 해시셋 검색 O(1) 평균 → O(m) 최대
            if phone[:i] in phone_set:
                return False  # O(1) 시간, O(1) 공간
    
    return True  # O(1) 시간, O(1) 공간

# 전체 시간복잡도: O(n) + O(n * m^2) = O(n * m^2)
# 전체 공간복잡도: O(n * m) (해시셋 저장)

동작 원리: - 모든 전화번호를 해시셋에 저장 - 각 번호의 모든 가능한 접두어를 생성하여 해시셋에서 검색

3.3.4 한 줄 해답 (정렬 + any 함수)

def solution(phone_book):
    # 사전순 정렬 - O(n log n) 시간, O(log n) 공간
    phone_book.sort()
    
    # any() 함수로 접두어 관계 확인 - O(n * m) 시간, O(1) 공간
    return not any(  # any(): 최악의 경우 O(n) 반복
        phone_book[i+1].startswith(phone_book[i])  # startswith: O(m) 시간
        for i in range(len(phone_book) - 1)  # 제너레이터: O(1) 공간
    )

# 전체 시간복잡도: O(n log n) + O(n * m) = O(n log n) (m << log n 일반적)
# 전체 공간복잡도: O(log n) (정렬 알고리즘 스택) + O(1) (제너레이터) = O(log n)

3.4 복잡도 비교표

방법	시간복잡도	공간복잡도	특징
정렬	O(n log n)	O(log n)	가장 효율적, 메모리 절약
해시셋	O(n×m²)	O(n×m)	구현이 직관적
한 줄 해답	O(n log n)	O(log n)	코드가 간결

3.5 왜 정렬 방법이 최적인가?

핵심 아이디어: 사전순 정렬 시 접두어 관계는 반드시 인접한 위치에 존재
시간 효율성: O(n log n) - 정렬 후 한 번의 순회만 필요
공간 효율성: O(log n) - 정렬 알고리즘의 스택 공간만 사용
단순함: 구현이 직관적이고 이해하기 쉬움

3.6 핵심 포인트

정렬의 활용: 사전순 정렬로 비교 대상을 대폭 축소
접두어 특성: A가 B의 접두어라면, 정렬 후 A는 B보다 앞에 위치
최적화: 모든 쌍 비교(O(n²)) → 인접 비교(O(n))

이 문제의 핵심은 “정렬을 통한 비교 대상 축소로 효율성을 극대화하는 것”입니다.

3.7 예제별 동작 과정

3.7.1 예제 1: `["119", "97674223", "1195524421"]` → 결과: false

정렬 방법: 1. 사전순 정렬: ["119", "1195524421", "97674223"] 2. 인접 비교: - “119”와 “1195524421”: "1195524421".startswith("119") → True - 접두어 관계 발견! → 답: false

3.7.2 예제 2: `["123", "456", "789"]` → 결과: true

정렬 방법: 1. 사전순 정렬: ["123", "456", "789"] (이미 정렬됨) 2. 인접 비교: - “123”과 “456”: "456".startswith("123") → False - “456”과 “789”: "789".startswith("456") → False - 접두어 관계 없음 → 답: true

3.7.3 예제 3: `["12", "123", "1235", "567", "88"]` → 결과: false

정렬 방법: 1. 사전순 정렬: ["12", "123", "1235", "567", "88"] 2. 인접 비교: - “12”와 “123”: "123".startswith("12") → True - 접두어 관계 발견! → 답: false