[Hash] Dictionary의 시간복잡도

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

프로그래머스

 

전화번호부에서 어떤 번호가 타 번호의 접두어일 경우를 검출하는 문제

 

전화번호부 list의 최대 len이 1,000,000, 전화번호 최대 len이 20이다.

만약 전화번호부를 for문 한번 돌리고, 각 전화번호를 모두 하나씩 끊어서 보는 연산까지 하면 

시간복잡도는 1,000,000*20 = 2*10e7,

이작업까지만 할 수 있음

 

그래서 Hash , 즉 python에서는 dictionary 자료형을 이용하기로 함.

 

dictionary는 해시 테이블을 기반으로 하여 키의 존재 여부를 평균적으로 O(1)으로 알 수 있음 -> 탐색에 효율적

 

즉, parameter로 오는 전화번호부 list를 for문을 통해 dictionary로 변환 (O(N) = 1,000,000)

 

그리고 for문으로 전화번호부를 다시돌리되,

이중포문으로 각 번호를 슬라이싱 (즉 'sleepy'를 's', 'sl', 'sle' .....로) (O(N*M) = 1,000,000*20) 하고

각 슬라이싱 된 parts가 dictionary에 있는지 탐색 (O(1))

있다면 False return

 

탐색이 O(1)이기 때문에 전체 시간복잡도가 O(N+M*N*1) = 21,000,000이므로 시간초과 되지 않는다!

 

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

hash 즉 파이썬의 딕셔너리는 한 element 저장,조회하는데에 O(1)이다
phone_book 길이 maximum이 1,000,000
그런데 한 번호 최대 길이 20
즉, 번호를 dict에 다넣고, 각 번호를 slicing한걸 다검사해도 O(N+NM) = 20*10e6

가능!
'''
    def solution(phone_book):
        dict = {}
        for num in phone_book:
            dict[num] = 1
        for num in phone_book:

                for i in range(1, len(num)):
                parts = num[:i]
                if parts in dict:
                    return False
        return True


print(solution(["119", "97674223", "1195524421"]))
print(solution(["123","456","789"]))

 

추가적으로 String slicing 할때 쓰는 [:n] -> n번째 전까지의 String을 반환하겠다

[n:] -> n번째부터 반환하겠다