heap에 대해 잘 알고 있다면 빠르게 해결가능한 문제!
python에서 heap사용을 위해 알아야 하는것,
import heapq 선언
import 해주어야 heap 사용이 가능하기때문에 문제 풀이시 꼭 선언해 주어야한다.
pop 및 push 하는 방법
heapq.heappush(heap, item)
: item 값을 heap으로 푸시한다.
heapq.heappop(heap)
: heap에서 가장 작은 항목을 팝하고 반환한다.
heapq.heappushpop(heap, item)
: 힙에 item을 푸시한 다음, heap에서 가장 작은 항목을 팝하고 반환한다.
heap사용 시, 가작 작은 값을 꺼내야하기 때문에 .sort()를 처음에는 해줬으나, heapq.heappop()함수 자체가 가장 작은 항목을 반환하기때문에 정렬할 필요가 없다.
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while(scoville[0] > K):
try:
mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
except:
return -1
heapq.heappush(scoville, mix)
answer += 1
return answer