문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항
scoville의 길이는 2 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
입출력 예
scoville K return
[1, 2, 3, 9, 10, 12] 7 2
입출력 예 설명
스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]

스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

코드

import heapq

def solution(scoville, K):
    answer = 0
    pop1 = 0
    pop2 = 0
    heapq.heapify(scoville)
    while scoville and scoville[0] < K:
        pop1 = heapq.heappop(scoville)
        pop2 = heapq.heappop(scoville)
        heapq.heappush(scoville, pop1+(pop2*2))
        answer += 1
        ## 히든케이스 !!, 만약 남은 힙의 길이가 1 일 경우 pop을 할 수 없다.
        if len(scoville) == 1 and scoville[0] < K:
            return -1
        
    return answer

배운것

힙(heapq)

• 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조
  : 각 노드의 key값이 해당 노드의 자식노드의 key값보다 작거나 크지 않은 완전 이진 트리
  : 키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음
  : 자식 노드의 최대 개수는 힙의 종류에 따라 다르지만 이진트리에서는 최대 2개(완전 이진트리를 사용한다고 가정)
  : i번째 노드의 자식노드가 2개인데 왼쪽 자식노드는 2i, 오른쪽 자식 노드는 2i+1, 부모노드는 i/2가 된다.

• 최대 힙(max heap)
  : 각 노드의 키 값이 그 자식노드의 키 값보다 작지 않은 힙
  : key(T.parent(v)) > key(v)

• 최소 힙(min heap)
  : 각 노드의 키 값이 그 자식노드의 키 값보다 크기 않은 힙
  : key(T.parent(v) < key(v))

• 시간 복잡도
  O(log n)

• 삽입연산
  : 1. 삽입하고자 하는 트리의 값을 트리의 가장 마지막 원소에 추가한다.
  : 2. 부모노드와의 대소관계를 비교하면서 만족할 때까지 자리 교환을 반복한다.

• 삭제연산
  : 1. 힙에서는 루트 노드만 삭제가 가능하므로 루트 노드를 제거한다.
  : 2. 가장 마지막 노드를 루트 노드로 이동시킨다.
  : 3. 자식 노드와 비교하여 조건이 만족할 때까지 이동시킨다.

heapq module

: 파이썬에서 제공하는 힙큐모듈, 일반적인 리스트를 min heap처럼 다룰 수 있게 해줌

• 모듈 임포트
  import heapq

• 노드 추가 : heappush 메소드를 이용
  heap = []
  heapq.heappush(heap, 1)

• 노드삭제 : heappop 메소드 이용
  가장 작은 원소를 꺼내어 리턴, 자동적으로 그 다음으로 작은 원소가 루트노드가 됨

return heapq.heappop(heap)
# 최솟값을 꺼내지 않고 리턴만 하려면 인덱스로 접근하기
print(heap[0])

• 기존에 사용한 리스트를 힙으로 변환하기: heapify 메소드 이용
  : 시간 복잡도는 O(n)

tmp = [7,5,8,3]
hrapq.heapify(tmp)

• 최대힙 만들기: 우선순위가 포함된 튜플 이용하기

import heapq
nums = [4,1,7,3,8,5]
heap = []
for num in nums:
	heapq.heappush(heap, (-num,num)) # 우선순위, 값
while heap:
	print(heapq.heapop(heap)[1]) # index 1