힙의 대표적인 문제 해결 : Spirer로 만들기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제를 해결하는 방법

음식물을 스코빌 지수로 정렬한 후 처음부터 하나씩 k와 비교하면($O(N)$) 작으면 섞고 배열에 넣는 과정을 반복하면($O(N) $), 전체 $O(N^2)$의 시간복잡도를 갖는다.

그렇다면 이 문제에서 가장 필요한 상황은 무엇일까요? -> 최소 힙?

더미

• 기능: 최대/최소 요소를 빠르게 찾기
• 계산
  • 히피파이 – $O(N\log N)$
  • 삽입 – $O(\log N)$
  • 제거 – $O(\log N)$

Python에서 힙 적용

import heapq
heapq.heapify(L) # 리스트 L로부터 min heap 구성
m = heapq.heappop(L) # min heap L에서 최소값 삭제(반환)
heapq.heappush(L, x) # min heap L에 원소 x 삽입

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