Lv2. 더 맵게

코딩테스트 연습 > 더 맵게

1. 풀이 설명

1. 최솟값을 계속해서 얻어야 하는 문제기 때문에 min heap을 사용한다.

2. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 가 언제일지를 고민해봐야 한다.

   • 가장 맵지 않은 음식(a)과 두 번째로 맵지 않은 음식(b) 2개의 아이템을 heap 에서 pop 하여 a+b*2로 계산한 새로운 1개의 아이템을 heap 에 넣게 된다. 즉, heap 아이템 수가 1개씩 줄어든다.

   • while문은 heap 의 최솟값이 K 미만일 때 계속 돌게 되는데, heap 의 개수가 1개이면서 최솟값이 K 미만일 때 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 케이스가 된다.

3. while 문을 1번 돌 때마다 count 를 더하여 반환한다.

2. 나의 풀이

import heapq

def solution(scoville, K):
    heap = []
    answer = 0
    for s in scoville:
        heapq.heappush(heap, s)
    
    while heap[0] < K:
        if len(heap) == 1:
            return -1
        mixed = heapq.heappop(heap) + heapq.heappop(heap) * 2
        heapq.heappush(heap, mixed)
        answer += 1
    return answer

3. 배운점

1. Heap (힙)

• 힙은 완전이진트리로 최솟값과 최댓값을 찾는 연산을 빠르게 수행할 수 있다.
  • Min Heap: 부모 키값이 자식 노트 키값보다 항상 작음 (<-> Max Heap)
  • 형제 노드 사이에 대소 관계 규칙 없음

2. Heap 사용법

import heapq

heap = [] # default: Min Heap

heapq.heappush(heap, item)  # push
heapq.heappop(heap)			# pop
heap[idx]					# 조회

# Max Heap
heapq.heappush(heap, (-item, item)) # (priority, value)