학습 주제
힙을 이용한 문제풀이

학습 내용

• import heapq
  힙 뒤에 q가 붙는 이유는 priority 성질이 있기 때문
  따로 연결리스트 사용하지 않고, 기존 사용배열 사용할 수 있다는 장점이 있음.

• 기존 배열을 이용해서 힙 구성함
  m = heapq.heappop(L)을 하게되면, min heap L에서 최솟값이 pop 되고, 빠진 힙이 다시 최소 힙을 유지하도록 구성되어 있음. O(nlogn) - 구조를 유지해야하므로
  heapq.heappush(L,x)

• 파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에, 최대 힙구현을 위한 트릭이 필요

• y = -x 로 원소들을 음수처리 후 힙 배열 생성, 삽입 시에 음수처리, 출력 후 음수를 씌워 원하는 답을 얻으면 된다.

• 파이썬 힙.push때 튜플식으로 넣으면 첫번째 원소가 정렬의 기준

import heapq

def solution(scovile, K):
    answer = 0
    # 디폴트는 min heap
    heapq.heapify(scovile)
    # 무한루프 형태로 구성
    # 중단조건.
    # 모든 음식이 K 이상의 스코빌을 가지게 되었거나,
    # 모든 음식을 섞었으나 K 이상의 스코빌 지수를 갖지 못한경우.
    # 이번엔 while에 조건을 명시하는 것보다, 위의 조건이 만족하는 경우에 break 하는 것이 편리하다고 판단함.
    while True:
        # min1을 가지고 종료 조건을 판단.
        min1 = heapq.heappop(scovile)
        # 제일 낮은 scovile 음식이 K 보다 같거나 크면,
        if min1 >= K:
            break
        # 제일 작은 수를 빼냈더니, 아무것도 남아있지 않은 경우,
        elif len(scovile) == 0:
            answer = -1
            break
        # 두번째로 안매운 스코빌 음식
        min2 = heapq.heappop(scovile)
        new_scoville = min1 + 2 * min2
        heapq.heappush(scovile, new_scoville)
        answer += 1

    return answer

복잡도

while True이지만, n-1 번만큼 반복, 최악은 n. .heappop() 연산 O(logn) .heappush(logn)

전체 복잡도는 n번을 반복하는데, 내부 연산중 최대 복잡도는 logn. 합하면 O(NlogN)
N^2와 NlogN의 복잡도 차이는 꽤 큼