[코딩테스트 고득점 Kit] 힙(Heap) 더 맵게 - Python

[문제 이해 및 풀이]

heap을 사용하는 문제여서 heapq를 사용해야겠다고 생각했다.

heapq.heappop()을 사용해서 최소값과 두번째로 작은 값을 변수에 저장을 한 뒤, heapq.heappush()를 사용해서 새로운 스코빌지수를 heap에 넣어주었다.

종료 조건인 모두 K를 넘을 경우에를 계산해주기 위해 heap의 성질을 생각하여 heap[0]가 K이상일 경우에 종료시켜주었다.

또 하나의 종료조건은 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우이다. 이 경우는 더 이상 섞을 음식이 없을 경우 즉, heap에 하나의 지수만 남아있는 경우에 해당된다. 따라서 이에 해당하는 if-break문을 만들어 넣어주었다.

 

---

[나의 코드]

import heapq
def solution(scovile,K):
    answer=0
    heap=[]
    for num in scovile:
        heapq.heappush(heap,num)
    while True:
        check=heapq.heappop(heap)
        if len(heap)==1:
            return -1
        if check>=K:
            break
        heapq.heappush(heap,check)
        min_1=heapq.heappop(heap)
        min_2=heapq.heappop(heap)
        heapq.heappush(heap,min_1+min_2*2)
        answer+=1
    return answer

---

문제출처 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게