[프로그래머스 | 코딩테스트 고득점 Kit] 해시 - 전화번호 목록

# 정렬을 활용한 O(NlgN) 풀이

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book) - 1):
        if phone_book[i + 1].startswith(phone_book[i]):
            return False
    return True

접두어가 존재한다면, 정렬한 뒤 두 번호는 항상 이웃하게 위치한다.

 

# 해시 set을 활용한 O(N) 풀이

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_book:
                return False
    return True

전화번호는 20자리 제한이 있기 때문에 4번째 줄의 for문에서는 상수 시간이 소요된다.

또한, 해시 Set은 O(1) 시간으로 데이터를 조회한다.

따라서 첫번째 for문에서 O(N) 시간이 소요됨을 알 수 있다.