https://school.programmers.co.kr/learn/courses/30/lessons/42577

방법 1: 정렬을 이용한 접근

정렬을 하면 접두사 관계에 있는 번호들이 인접하게 됨
인접한 번호를 비교하여,
첫 번째 번호가 두 번째 번호의 접두사인지 확인

def solution(phone_book):
    # 전화번호부를 정렬합니다.
    phone_book.sort()
    
    # 인접한 번호들끼리 비교합니다.
    for i in range(len(phone_book) - 1):
        # 현재 번호와 다음 번호를 비교합니다.
        if phone_book[i] == phone_book[i + 1][:len(phone_book[i])]:
            return False
            
    return True

방법 2: 해시셋을 이용한 접근

모든 전화번호를 해시셋에 추가
각 전화번호에 대해
가능한 모든 접두사를 해시셋에서 확인

def solution(phone_book):
    phone_set = set(phone_book)
    
    for number in phone_book:
        for i in range(1, len(number)):
            # 현재 번호의 접두사를 확인합니다.
            if number[:i] in phone_set:
                return False
                
    return True

알고리즘 분석

정렬 방법:

시간 복잡도: 𝑂(𝑛log𝑛) (정렬)
공간 복잡도: 𝑂(1) (정렬을 제외한 추가 메모리 사용 없음)

해시셋 방법:

시간 복잡도: 𝑂(𝑛⋅𝑚) (n은 전화번호 개수, m은 전화번호의 최대 길이)
공간 복잡도: 𝑂(𝑛) (해시셋을 저장하기 위한 공간)

정렬을 이용한 방법이 더 효율적이며,
일반적으로 더 빠르게 동작