더 맵게 문제링크

우선순위큐란?

개념

우선순위큐(Priority Queue)는 데이터를 저장하고 검색하는 자료구조로, 각각의 데이터는 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 처리되는 특징을 가지고 있습니다. 일반적으로, 우선순위 큐는 최소값(Min Heap) 또는 최대값(Max Heap)을 빠르게 찾는데 사용되며, 이를 기반으로 다양한 알고리즘들이 구현될 수 있습니다.
우선순위큐는 일반 큐(Queue)와 유사하지만, 큐에 데이터를 삽입할 때 우선순위에 따라 정렬되고, 가장 높은 우선순위를 가진 데이터가 가장 먼저 추출되는 차이점이 있습니다. 삽입, 삭제, 검색 연산이 빠르게 수행되어야 하므로 일반적으로 힙(Heap) 자료구조를 사용하여 구현됩니다.

예제코드

import heapq

# 빈 우선순위큐 생성
pq = []

# 데이터 삽입
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 1)
heapq.heappush(pq, 5)

# 데이터 추출 (우선순위가 가장 높은 데이터가 추출됨)
while pq:
    print(heapq.heappop(pq), end=' ')
# 출력: 1 1 3 4 5

문제1-[프로그래머스]더 맵게

런타임에러 나는 코드

import heapq as hq

def solution(scoville, K):
    cnt=0
    
    a=[]
    for s in scoville:
        hq.heappush(a,s)

    while a[0]<K:
        cnt+=1
        new_scoville=hq.heappop(a)+hq.heappop(a)*2
        hq.heappush(a,new_scoville)
    
    if sum(a) <K:
        return -1
    return cnt

    

print(solution([1, 2, 3, 9, 10, 12],7))

수정한 코드

런타임 에러가 나는 부분을 예외처리 해주었다.

import heapq as hq

def solution(scoville, K):
    cnt=0
    
    a=[]
    for s in scoville:
        hq.heappush(a,s)

    while a[0]<K:
        try:
            cnt+=1
            new_scoville=hq.heappop(a)+hq.heappop(a)*2
            hq.heappush(a,new_scoville)
            
        except:
            return -1
    
    return cnt

    

print(solution([1, 2, 3, 9, 10, 12],7))