[python 힙] 프로그래머스 - 더 맵게

레벨 2

 

 

heapq (우선 순위 큐) 개념

 

import heapq

list1 = [5,2,6,3,4,1]
heap = []
for i in list1:
	heapq.heappush(heap,i)
print(heap)

[1, 3, 2, 5, 4, 6]

 

heapq는 우선 순위 큐로 heappush() 함수를 사용하면,  k번째 인덱스에 있는 원소가 2k+1, 2k+2 번째 인덱스에 있는 원소보다 같거나 작습니다. 예를 들어, 3이라는 원소는 인덱스 1이고, 인덱스 2k+1(3), 2k+2(4) 에 해당하는 5와 4보다 작은 값을 갖습니다. 

 

import heapq

list1 = [5,2,6,3,4,1]
heap = []
for i in list1:
	heapq.heappush(heap,i)

sort = []
while heap:
    sort.append(heapq.heappop(heap))
print(sort)

 

이 때, heappop() 함수는 heap 리스트를 받아서 원소 값이 가장 작은 값부터 추출을 합니다. 중요한 점은 heap 리스트의 모든 원소가 heappush() 함수로 추가가 되어 있기 때문에 최솟값부터 추출할 수 있다는 것입니다. 만일 heap 리스트가 무작위로 배치되어 있다면 heapify() 함수를 사용합니다. 

 

import heapq

heap = [5,2,6,3,4,1]
heapq.heapify(heap)

sort = []
while heap:
    sort.append(heapq.heappop(heap))
print(sort)

 

 

 

문제풀이

 

import heapq

def solution(scovile, K):
    heap=[]
    # 스코빌 지수 리스트 heapq로 배치
    for i in scovile:
        heapq.heappush(heap,i)
    count=0
      
    while True:
        a = heapq.heappop(heap)
        if a >= K :
            return count
        try :
            b = heapq.heappop(heap)
        except:
            return -1               # heap 이 비어있을 경우
        heapq.heappush(heap,a+2*b)
        count+=1