안녕하세요. 탁입니다.

세번째 문제는 해시 유형의 Level2 문제인 '전화번호 목록' 입니다.

전화번호 목록

문제 설명

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

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

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

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

제한 사항

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

입출력 예

입출력 예
2열 × 3행
phone_bookreturn
["119", "97674223", "1195524421"]false
["123","456","789"]true
["12","123","1235","567","88"]false

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

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

입출력 예 #3

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

나의 풀이

문제 접근 아이디어는 이랬습니다.

phone_book의 내용물을 길이 순으로 정렬한 뒤에

앞에서부터 뒤로 이동하면서

뒤의 내용물이 앞의 내용물로 시작하는지를 확인해서

하나라도 검출되는 순간 False를 반환한다.

1. 초기화 상태

Python
3 lines
def solution(phone_book):
    answer = True
    return answer

2. 풀이 과정

Python
8 lines
def solution(phone_book):
    answer = True # 초기값을 True로 설정하여 모두 값을 확인했을 때에도 시작되는 값이 없다면 True 그대로 반환하도록
    sorted_phone_book = sorted(phone_book, key=lambda p: (len(p))) # 길이를 기준으로 정렬
    for i, p in enumerate(sorted_phone_book): # 행 번호를 사용하여 비교군을 만들기 위해서 enumerate 사용
        for p2 in sorted_phone_book[i+1:]: # 비교군 리스트 선언과 함께 2중 for 문 선언
            if (p2.startswith(p)): # startswith() 사용해서 비교
                return False # 하나라도 다른 번호의 접두어임이 확인된다면 False 반환하고 끝
    return answer # 하나도 없다면 초기값인 True 반환하고 끝

3. 답안 확인

Python
8 lines
def solution(phone_book):
    answer = True
    sorted_phone_book = sorted(phone_book, key=lambda p: (len(p)))
    for i, p in enumerate(sorted_phone_book):
        for p2 in sorted_phone_book[i+1:]:
            if (p2.startswith(p)):
                return False
    return answer

예시 테스트케이스도 모두 성공했으니 답안을 제출했지만

효율성 테스트에서 실패 (시간 초과) 가 4개 중 2개 나왔습니다.

채점 결과

  • 정확성: 83.3
  • 효율성: 8.3
  • 합계: 91.7 / 100.0

무엇이 문제인지 AI를 활용해 학습해보겠습니다.

제출 답안 분석 및 복잡도 확인

Gemini의 도움을 받아 저의 답안에 대한 평가를 해봅니다.

  1. 시간 복잡도: 최악 O(N2×L)O(N^2 \times L) (시간 초과 발생)
  • 길이 기준 정렬: 길이 순으로 정렬하는 데 O(Nlog⁡N)O(N \log N)이 소요됩니다.
  • 2중 루프 전수조사:
    • 전화번호 중 접두어 관계가 전혀 없는 경우(반환값이 True인 케이스), 안쪽 루프가 한 번도 조기 종료되지 않고 끝까지 수행됩니다.
    • 이때 내부 비교 횟수는 N(N−1)2\frac{N(N - 1)}{2}번입니다.
    • 각 비교마다 startswith를 수행하므로 문자열의 최대 길이 LL (L≤20L \le 20)을 고려하면 총 연산량은 O(N2×L)O(N^2 \times L)입니다.
  • 제한 조건 대입: N=1,000,000N = 1,000,000일 때 비교 횟수만 약 5×10115 \times 10^{11}회에 달합니다. 파이썬 환경의 1초당 연산 가능 횟수가 약 2×107∼1082 \times 10^7 \sim 10^8회인 점을 감안하면 수백 초 이상 소요되어 효율성 테스트를 통과할 수 없습니다.
  1. 공간 복잡도: O(N)O(N)
  • sorted_phone_book 리스트가 NN개의 문자열 참조를 유지하므로 O(N)O(N) 메모리가 사용됩니다.
  • 루프가 돌 때마다 sorted_phone_book[i+1:] 슬라이싱을 호출하여 최대 크기 NN의 새로운 서브리스트를 매번 힙에 할당하고 해제하므로 극심한 가비지 컬렉션(GC) 및 메모리 복사 오버헤드가 누적됩니다.
  1. 핵심 패인
  • 길이를 기준으로 정렬하면 "나보다 긴 모든 문자열"을 전부 대조해 보아야 합니다.
  • 조기 반환(return False)은 접두사를 빠르게 찾았을 때만 동작하며, 접두사가 존재하지 않는 반례에서는 아무런 최적화 효과를 내지 못합니다.

AI 추천 답안

아래는 Gemini가 작성해 준 내용입니다.

사용 AI 모델: Gemini 3.8 Flash (Extended)

추천 1: 사전순 정렬 후 인접 원소 1:1 비교

문자열의 기본 정렬 기준인 사전순(Lexicographical order) 정렬을 활용하는 방식입니다.

Python
10 lines
def solution(phone_book):
    # 문자열 사전순 정렬 (기본 sort)
    phone_book.sort()
    
    # 바로 다음 번호와만 1:1 접두어 관계 확인
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
            
    return True
  • 동작 원리: 문자열을 사전순으로 정렬하면 어떤 번호 AA가 번호 BB의 접두사일 때, AA와 BB는 반드시 정렬된 배열 안에서 서로 인접하여 나란히 배치됩니다.
    • 예: ["119", "97674223", "1195524421"] →\rightarrow ['119', '1195524421', '97674223']
  • 2중 루프가 필요 없이 인접한 두 원소(N−1N-1쌍)만 11회 검사하므로 연산 횟수가 극적으로 줄어듭니다.

추천 2: 해시 셋(Hash Set) 조회 (문제 본래 출제 의도)

전체 번호를 집합에 넣은 뒤, 각 번호의 부분 문자열이 집합에 존재하는지 확인하는 해시 기법입니다.

Python
12 lines
def solution(phone_book):
    hash_set = set(phone_book)
    
    for phone_number in phone_book:
        prefix = ""
        # 자기 자신을 제외한 1글자부터 (전체 길이 - 1)글자까지의 접두어 생성
        for digit in phone_number[:-1]:
            prefix += digit
            if prefix in hash_set:
                return False
                
    return True
  • 동작 원리: 각 전화번호의 최대 길이가 L≤20L \le 20으로 매우 짧다는 점을 공략합니다. 각 번호당 최대 19번만 해시 셋(in hash_set)의 O(1)O(1) 조회를 수행하므로, N=1,000,000N=1,000,000이어도 약 1.9×1071.9 \times 10^7번 연산 이내에 확정 종료됩니다.

제출 답안 vs AI 추천 답안 비교

제출 답안 vs AI 추천 답안 비교
4열 × 4행
비교 항목제출 답안 (길이 정렬 + 조기반환 브루트포스)추천 답안 1 (사전순 정렬 + zip 인접 비교)추천 답안 2 (해시 셋 조회)
최악 시간 복잡도O(N2×L)O(N^2 \times L)O(Nlog⁡N×L)O(N \log N \times L)O(N×L)O(N \times L)
공간 복잡도O(N)O(N) (반복 슬라이싱 복사 오버헤드)O(1)O(1) (제자리 sort 사용 시)O(N×L)O(N \times L) (해시 셋 공간)
효율성 테스트실패 (시간 초과)통과 (약 0.15~0.25초)통과 (약 0.25~0.40초)
루프 반복 횟수최악 N(N−1)2\frac{N(N-1)}{2}회 (≈5×1011\approx 5 \times 10^{11})항상 N−1N-1회 (≈106\approx 10^6)최대 N×(L−1)N \times (L-1)회 (≈1.9×107\approx 1.9 \times 10^7)

제출 답안에서 return False를 추가한 것은 유의미한 시도였으나, 정렬 기준이 문자열의 본질적인 특성(사전순 접두어 응집성)과 맞지 않아 최악의 경우를 방어하지 못했습니다.

실제 코딩테스트에서는 별도 메모리를 생성하지 않고 4줄 만에 해결되는 추천 1(사전순 정렬)이 가장 빠르고 강력하며, 면접에서 해시 카테고리 본래의 시간 복잡도 유도 과정을 질문받을 때는 문자열 길이 상수 제약(L≤20L \le 20)을 설명할 수 있는 추천 2(해시 셋)를 활용하는 것이 적합합니다.

회고

일단, 아이디어부터가 한 단계 부족했었네요.

단순히 길이 순으로 정렬한 뒤에 비교하는 것보다 사전순으로 정렬하게되니 큰 차이가 발생하는 군요.

그리고 사전 순 정렬의 핵심은 인접 대상과의 비교만으로 연산 횟수를 엄청 낮춘 것...

이 아이디어를 떠올릴 수 없다면 추천2번의 본래 출제 의도처럼 푸는 것이 손에 익어야겠죠.

공부할 길이 멉니다.

바로 다음 문제도 또 공부해보겠습니다.

감사합니다.