[해시] 전화번호 목록

1. 문제

programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

2. 접근 방법

해시로 접근하지 않으면 시간초과가 납니다요

3. 코드

python

def solution(phone_book):
    answer = True
    hash = {}
    for phone in phone_book:
        hash[phone] = 1
    for phone in phone_book:
        temp = ""
        for num in phone:
            temp += num
            if temp in hash and temp != phone:
                answer = False
                break
    return answer

4. 마치며

문제 분류가 해시지만 리스트로 접근해보았다. 

그랬더니 당근빠따 시간초과가 났다.

흠 ~!

그래서 찾아본 결과 dict와 list는 탐색하는 경우에 걸리는 시간 복잡도가 각각 O(1), O(n)이었다.

참고한 링크는 다음과 같다.

huidea.tistory.com/6

[프로그래머스][hash] 전화번호목록 python (200715)

gomguard.tistory.com/181

[Python] List, Dict 시간 복잡도 (Big O)