8. 힙(heap)

명예의 전당(1) - https://school.programmers.co.kr/tryouts/85933/challenges

heapq 모듈의 기본 사용법 활용 → heapify, heappush, heappop

from heapq import heappush, heappop, heapify
def solution(k, score):
    heap = []
    heapify(heap)
    ans = []
    for s in score:
        heappush(heap, s)
        if len(heap) > k:
            heappop(heap)
        ans.append(heap[0])
    return ans

 

---

더 맵게 - https://school.programmers.co.kr/tryouts/85934/challenges

불가능한 경우 예외 처리 주의

from heapq import heapify, heappush, heappop
def solution(scoville, K):
    heapify(scoville)
    ans = 0
    while len(scoville) > 1 and scoville[0] < K:
        min_1 = heappop(scoville)
        min_2 = heappop(scoville)
        new_s = min_1 + min_2 * 2
        heappush(scoville, new_s)
        ans += 1
    if scoville[0] < K:
        return -1
    return ans

 

---

야근 지수 - https://school.programmers.co.kr/tryouts/85935/challenges

max heap 만들어서 사용하면 빠름 → list에서 매번 sort하면 시간 초과 뜸

from heapq import heapify, heappush, heappop
def solution(n, works):
    works = [-work for work in works]
    heapify(works) # max heap
    
    for _ in range(n):
        max_work = heappop(works)
        if max_work < 0:
            heappush(works, max_work + 1)
        else:
            break
    
    return sum(work ** 2 for work in works)