프로그래머스 - Heap - 더 맵게

09 Mar 2020

문제

입력

---

나의 처음 코드

힙 카테고리에 있는 문제들은 대부분 우선순위 힙을 구현하거나, heapq를 import해서 쓰거나 둘 중에 하나다. 알고리즘 문제와 뭔가 맞지 않는 문제들만 제시되어 있는 느낌이다? 그러나, 우선순위 minheap, maxheap가 어떻게 작동되는지, 어떤식으로 구현하는지는 필수로 알고있으면 좋을 것 같다. 이 문제는 풀이방법이 문제에 나와있는거랑 마찬가지기 때문에, heapq만 import해서 문제를 풀었다. 코드가 매우 직관적이므로 설명을 생략하도록 하겠다.

from heapq import heapify, heappop, heappush
def solution(scoville, K):
    heapify(scoville)
    count = 0
    while True:
        min1 = heappop(scoville)
        if min1 >= K:
            return count
        elif len(scoville) == 0:
            return - 1
        min2 = heappop(scoville)
        count += 1
        heappush(scoville, min1 + min2 * 2)

3가지 heapify, heappop, heappush를 볼 수 있을 것이다.
heapify의 경우에는 보통 리스트를 우선순위 힙으로 만들고 싶을 때 사용된다. 예제는 다음과 같다.

list_a = [2,1,4,3]
heapify(list_a)
print(*list_a)
#결과는 1 2 4 3 이 될 것이다.

heappop과 heappush경우에는 list의 pop과 append와 유사하다.
어려운 문제는 아니므로! 쉽게 풀 수 있을 것이다!