[Programmers] Level 2. 전화번호 목록

🔗 Problem Link

Level 2. 전화번호 목록

❔Thinking

• phone_book의 각 번호를 접두어로 하는 번호가 있는지 확인한다.
• 해당 번호를 접두어로 가지면서 그 번호가 아닌 경우가 있다면 false를 반환한다.

💻Solution

1. Brute Force (시간초과)

def solution(phone_book):
    answer = True
    phone_book.sort()
    N = len(phone_book)
    for i in range(N-1):
        for j in range(i+1, N):
            if phone_book[j].startswith(phone_book[i]):
                answer = False
                break
    return answer

2. Hash Table

def solution(phone_book):
    phone_dict = {number : number for number in phone_book}
    for phone_num in phone_book:
        for i in range(1,len(phone_num)):
            if phone_num[:i] in phone_dict and phone_dict[phone_num[:i]] != phone_num:
                return False
    return True

🗝️keypoint

• Hash Table의 평균 시간 복잡도는 $O(1)$이다. (충돌이 발생할 경우 $O(n)$)
• return을 만나면 해당 함수는 종료된다. -> 코드 수를 줄일 수 있다.