[Heap] heapq의 시간복잡도(1)

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

프로그래머스

Heap에 대한 자료구조를 이해하지 못하면 효율성 테스트에서 통과하지 못한다.

 

Heap 써야만 하는 이유! :

위 문제의 관건은 가장작은 두 값으로 연산을 한 후에, '정렬을 할때' 이다.

O( 앞에_두값_연산_횟수 * 정렬_시_시간 ) 

len(scoville)의 최대값이 1,000,000이므로  O(N) = 1,000,000 *정렬_시_반복_횟수 <= 20,000,000 이어야한다.

즉, 정렬_시_시간 <= 20 이어야한다.

정렬_시_반복_횟수 이 어떻게 <= 20일 수 있을까 생각하면, 이는 lgN 밖에는 답이 없다는 생각에 다다르고 ( lg(10e6) = 2lg(10e3) ~= 2lg(2e10) = 20 )

결국 push 할때 시간복잡도가 lgN인 heap을 써야한다!!

 

자 Python에 해당하는 heap과 관련된 라이브러리,function은 영어단어 외우듯이 다시 한 번 외워보자

 

import heapq         #python에서의 heap 자료구조

heapq.heapify(리스트)        #리스트를 heap으로 변환, 시간복잡도 O(len(리스트))

heapq.heappop(힙큐)            #힙의 root pop , 시간복잡도 O(lg(len(큐)))

heapq.heappush(힙큐, element)   #힙큐에 element를 heap자료구조로 push , 시간복잡도 O(lg(len(큐)))

 

def solution(scoville, K):
    heapq.heapify(scoville)             #O(N)
    cnt = 0

    while scoville[0] < K:              #O(N)
        if len(scoville) == 1:
            return -1
        cnt += 1
        min1 = heapq.heappop(scoville)  #O(log n)
        min2 = heapq.heappop(scoville)  #O(log n)
        heapq.heappush(scoville, min1 + (min2 * 2))
                                        # O(log n)

    return cnt

 

최종 시간복잡도 : O(N) + O(N) * { O(lg N) * 3 }  =  O( N + 3N(lgN) ) = O( Nlg N ) = 10e6 * lg(10e6)  ~= 10e6 * 20 = 2억 

딱 떨어진다...

 

조만간 heap 자료구조를 제대로 파서 정리해야겠다