[프로그래머스] 42626 더맵게

힙이란?

• 힙은 최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해서 고안된 완전 이진트리로 구성된 자료구조이다.
  (여기서 완전 이진트리란, 자식노드를 왼쪽부터 오른쪽으로 채워넣는 것을 뜻한다)
• 일반적으로 root에 최소값이 오는 최소힙과 최대값이 오는 최대힙으로 구분된다.
• 같은 완전 이진트리라 그런지 이진탐색트리와도 비슷하지만, 이진탐색트리의 경우 좌우와 상관없이 부모노드가 자식노드보다 작다/크다의 조건맞을 갖는 트리이기 때문에 조금다르다.

최소 Heap

최소 Heap은 말 그대로 값이 작은 값을 항상 부모 노드로 올림으로써 루트에는 항상 가장 작은 값이 오도록 하는 것을 뜻한다.

최대 Heap

최대 Heap은 최소 Heap과 반대로 가장 큰 값을 부모노드로 계속 올림으로써 루트에는 항상 가장 큰 값이 오도록 하는 것을 뜻한다.

---

문제 보러가기

문제 설명

코드

import heapq

def solution(scoville, K):
    heapq.heapify(scoville)
    cnt = 0

    while scoville[0] < K:
        if len(scoville) == 1:
            return -1
        cnt += 1
        first = heapq.heappop(scoville)
        second = heapq.heappop(scoville)
        heapq.heappush(scoville, first + second * 2)

    return cnt

📌 파이썬의 heapq 모듈은 최소 힙 자료구조를 제공함

heapq.heapify(list) : 기존의 list를 힙으로 변환 (인덱스 0번에 최솟값이 위치함)
heapq.heappop(list) : list의 가장 작은 값 삭제 후, 그 값을 리턴
heapq.heappush(list, number) : 힙에 원소(number) 추가

시간 복잡도 , 공간복잡도: O(n)