더 맵게 → heap★★

나의 풀이 

import heapq 
def solution(scoville, K):
    cnt=0
    heap=[]
    for x in scoville:
        heapq.heappush(heap, x)

    if heap[0]>=K:
        return cnt
    
    while(len(heap)>1):
      
		첫번째로 가장 작은 원소를 pop한다.
        min1=heapq.heappop(heap)
        또 남아있는 것 중에서 가장 작은 원소를 pop한다.
        min2=heapq.heappop(heap)
        new_scoville=min1+(min2*2)
      
        heap.append(new_scoville)
        cnt+=1
        if heap[0]>=K:
            return cnt
    return -1

 

힙(자료구조)의 활용

 ▶ import heapq 

  heap =[]

  heapq.heappush(heap, item) : item을 heap에 추가

  heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴.  비어 있는 경우 IndexError가 호출됨. 

  heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )