Step 5: 힙(Heap) 대표 문제 풀이: 더 맵게

강의

"힙"은 최대 / 최소 원소를 빠르게 찾을 수 있는 알고리즘 입니다.

힙은 완전 이진 트리 자료구조를 통해 구현합니다.

• max heap
• min heap

 

연산

• heapify : 힙 구성. O(N log N) 
• insert : 삽입. O(log N)
• remove : 삭제. O(log N)

import heapq

heapq.heapify(L)
heap.heappush(L, x)
min = heapq.heappop(L)

 

응용

• 정렬 (heapsort)
• 우선 순위 큐 (priority queue)

 

 

Step 5-3: 풀어서 내 것으로 만들자! 더 맵게

⭐ heapq 라이브러리를 이용하여 푸는 문제!

import heapq

def solution(scoville, k):
    heapq.heapify(scoville)
    
    cnt = 0
    
    while scoville[0] < k:
        if len(scoville) < 2:
            cnt = -1
            break
            
        cnt += 1
        
        new = heapq.heappop(scoville) + heapq.heappop(scoville)*2   
        heapq.heappush(scoville, new)
        
    return cnt

⭐ 힌트 풀이 :