[프로그래머스/Python] 더 맵게(힙)

코딩테스트 연습 - 더 맵게

 

이 문제는 음식을 섞을 때마다 다시 정렬을 계속 해야하는 문제를 극복하기 위해 우선순위큐를 이용한 풀이를 할 수 있다. python에서 우선순위 큐는 queue 모듈의 PriorityQueue를 통해 사용할 수 있지만 결국 이 클래스의 내부 구조는 heapq를 사용하도록 구현되어 있으므로 heapq를 이용하여 풀이하면 된다.

 

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while True:
        min1 = heapq.heappop(scoville)
        if min1 >= K:
            break
        if len(scoville) == 0:
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        heapq.heappush(scoville, min1 + min2*2)
        answer += 1
    
    return answer