Step 5: 힙(Heap) 대표 문제 풀이: 더 맵게

---

문제분석

반복문을 이용한 풀이

• 최악의 경우 : 수가 하나 남을 때까지 섞어야 하는 경우 (n-1)
• 각 단계("섞는 일")에서 요구되는 계산량:
  정렬된 리스트에 순서 맞추어 원소 삽입
  O(N)

• 전체 문제 풀이의 복잡도 : O(n^2)
  지나치게 높다

복잡도를 줄이기 위한 방법

• 최소/최대 원소를 빠르게 꺼낼 수 있으면 좋겠는데!
• 힙(heap)
  • max heap
  • min heap

---

알고리즘

필요 개념

힙

• 성질 : 최대/ 최소 원소를 빠르게 찾을 수 있음
• 연산 : 힙 구성(heapify) O(NlogN)
  삽입(insert) O(NlogN)
  삭제(remove) O(NlogN)

힙의 구현

힙의 응용

• 정렬 (heapsort)
• 우선 순위 큐 (priority queue)

python을 이용한 풀이

python 에서 heap 적용

import heapq
heapq.heapify(L)		# 리스트 L로부터 min heap 구성
m = heapq.heapop(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.heappop(scoville)
        new_scoville = min1 + 2 * min2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer

시간복잡도

• 이렇게 설계한 알고리즘의 복잡도는?
  O(NlogN)

---