[코딩테스트] 전화번호 목록 with Python

아이디어

def solution(phone_book):
    for a in phone_book:
        for b in phone_book:
            if a.startswith(b) and a != b:
                return False
    return True

그냥 문제 보자마자 이 코드가 생각났다.
물론 정확성 테스트는 그냥 통과하는데 효율성 테스트에서 막힌다.

다른 방법을 생각해야 했다.

제한 사항을 확인하자.

phone_book의 길이가 1,000,000 이하라고 한다.
최대 O(n log n) 으로 풀어야 한다.

문제 풀이 코드

def solution(phone_book):
    phone_book.sort()  # 1
    for a,b in zip(phone_book, phone_book[1:]): # 2
        if b.startswith(a):
            return False
    return True

#1

문자열 정렬로 접두어 번호가 비교되는 번호의 앞에 오도록 한다.

#2

바로 앞, 뒤만 체크하며 지나가 시간 복잡도가 줄어든다 O(N)