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

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

프로그래머스

---

문제 풀이 방법

만약 음식을 스코빌 지수로 정렬한 다음 앞에서부터 하나씩 k와의 비교를 통해($O(N)$) 작으면 섞어주고 다시 배열에 삽입해 주는 과정을 반복하게 된다면 ($O(N)$) 총 $O(N^2)$의 시간 복잡도를 갖게 된다.

 

📌 그렇다면 이 문제에서 가장 필요한 상황은 무엇일까 삽입과 조회를 할때 계속 최솟값을 찾을수 있는 상황. -> 최소힙?

 

힙(Heaps)

• 성질: 최대/최소 원소를 빠르게 찾을 수 있음
• 연산
  • 힙 구성(heapify) - $O(N\log N)$
  • 삽입(insert) - $O(\log N)$
  • 삭제(remove) - $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