99클럽 코테 스터디 5일차 TIL 힙 :프로그래머스 LV.2 더 맵게 with Python

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

문제는 위쪽에서!

 

힙을 사용하면 쉽게 풀 수 있는 문제였다!

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while True:
        # 가장 맵지 않은, 두번째로 맵지 않은
        first, second = heapq.heappop(scoville), heapq.heappop(scoville)
        
        # 가장 맵지 않은게 K를 넘으면 모든 음식 스코빌 지수 K 넘음
        if first >= K:
            break
            
        heapq.heappush(scoville, first+second*2)
        answer += 1
        
        # scoville 리스트에 한개가 남았을 때 K보다 작으면 실패
        if len(scoville) == 1:
            if scoville[0] < K:
                answer = -1
            break
        
    return answer

heapq 에서 기본적으로 제공하는 힙은 min heap 이기 때문에 만약 max heap을 사용하고 싶다면 * -1 을해서 사용하면 된다.

 

Max Heap 예시

import heapq

x = [1, 5, 3, 9, 7]
hq = []

# hq = [-1, -5, -3, -9, -7]
for ele in x:
  hq.append(-ele)
  
# hq = [-9, -7, -5, -3, -1]
heapq.heapify(hq)

# 9 7 5 3 1
while hq:
  print(-heapq.heappop(hq))