[프로그래머스] 더 맵게 파이썬 heapq

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

프로그래머스

 

내 코드

import heapq


def solution(scoville, K):
    heapq.heapify(scoville)
    cnt = 0
    while scoville[0] < K:
        if len(scoville) >= 2:
            min_1 = heapq.heappop(scoville)
            min_2 = heapq.heappop(scoville)
            heapq.heappush(scoville, min_1 + (min_2 * 2))
            cnt += 1
        else:
            return -1
    return cnt

---

 

Review

 

문제를 풀기 위해 파이썬 내부에 미리 구현되어 있는 heapq 모듈을 사용했다.

힙의 중요한 특성은 가장 작은 요소가 항상 루트인 heap[0]이라는 것이다.

따라서 heappop 은 가장 작은 항목을 반환한다.

힙을 만들려면

1. []로 초기화된 리스트를 사용

2. 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환 가능

 

이 문제에서는 2번 방법으로 힙으로 만들어 주었다.

🔥 scoville[0] 은 힙에서 가장 작은 값이다.

그 값이 K 보다 작으면 반복문이 돌아가 첫번째로작은값,  두번째로 작은 값을 연산해 다시 push해주는 구조로 코드를 짰다.

힙의 원소가 하나가 남을때까지도 K보다 작다면 -1을 리턴 해주면 된다.

 

⭐️ 파이썬 heapq 간략하게 정리

 

• heapq.heappush(heap, item)
  
  힙의 불변성을 유지하면서, item 값을 heap으로 push 해준다.
  

 

• heapq.heappop(heap)
  
  힙의 불변성을 유지하면서, heap에서 가장 작은 항목을 pop()하고 반환한다. 힙이 비어 있으면, IndexError가 발생한다.
  
  heappop(heap) 하지 않고 가장 작은 항목에 액세스하려면, heap[0]을 사용하면 된다.
  

 

• heapq.heapify(x)
  
  리스트 x를 선형 시간으로 제자리에서 히프로 변환해준다.

 

자세한 설명, 함수설명은 heap 파이썬 공식 문서