[힙] 더 맵게

더 맵게

매운 것을 좋아하는 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

---

나의 풀이

테케는 맞았지만 효율성을 다 틀렸다(이건 힙으로 풀지 않아서..)

from collections import deque
def solution(scoville, K):
    cnt= 0
    fail = -1
    scoville.sort()
    queue = deque(scoville)
    
    #while len(queue) > 1:
    # 뭔차이지..? 
    #q[0]이 K 이상인지 확인하는 게 이미 음식을 섞고 난 후이기 때문에 
    # k = 4, queue = [5,6,7] 인 경우 섞을 필요가 없기 때문에
    while queue[0] < K and len(queue) > 1:
        first = queue.popleft()
        second = queue.popleft()
       
        spicy = first + (second * 2)
        cnt += 1
        queue.append(spicy)
   
        queue = deque(sorted(list(queue)))  
        if all(value >= K for value in queue):
            break

    if all(value >= K for value in queue):
        return cnt
    else:
        return fail

힙을 사용한 풀이

import heapq

def solution(scoville, K):
    answer = 0
    scoville.sort()
    while scoville[0] < K:
        if len(scoville) <= 1:
            return -1
        else:
            small = heapq.heappop(scoville)
            small2 = heapq.heappop(scoville)
            heapq.heappush(scoville, 
            (small + (small2 * 2)))
            answer += 1
    return answer

TIL

🌷 힙(Heap)

heapq는 파이썬의 내장 모듈로서 힙(Heap) 자료구조를 제공
힙은 최솟값 또는 최댓값을 빠르게 찾아낼 수 있는 효율적인 자료구조로, 최소 힙은 부모 노드의 값이 자식 노드의 값보다 항상 작은 힙을 의미
가장 작은 요소가 항상 루트인 heap[0] (기본 최소힙)

heapq 모듈은 리스트를 힙으로 다룰 수 있도록 함수와 알고리즘을 제공

• heappush : 힙에 원소 추가
• heappop : 힙에 가장 작은 원소 제거
• heapify : 리스트를 힙으로 변환 O(N)
• 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

힙은 주로 우선순위 큐 등에 사용되며, 최소값 또는 최대값을 빠르게 찾아야 하는 상황에서 유용

🍀 최대힙

기본적으로 heapq 모듈은 최소힙을 지원하므로, 값을 음수로 변환하여 최대힙을 구현
값을 넣을 때 음수로 바꾸고, 값을 뺄 때 다시 원래 값으로 바꾸는 방식

import heapq

def max_heap_push(heap, item):
    heapq.heappush(heap, -item)

def max_heap_pop(heap):
    return -heapq.heappop(heap)

# 사용 예시
max_heap = []
max_heap_push(max_heap, 5)
max_heap_push(max_heap, 3)
max_heap_push(max_heap, 7)
print(max_heap)  # 출력: [-7, -5, -3]

print(max_heap_pop(max_heap))  # 출력: 7
print(max_heap)  # 출력: [-5, -3]

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item)) #튜플

print(max_heap)

max_item = heapq.heappop(max_heap)[1] #인덱싱으로 접근
print(max_item) #9

🌼 list.sort(), sorted(list)

sort() 메서드는 리스트를 직접 정렬하며, sorted() 함수는 정렬된 새로운 리스트를 반환

my_list = [4, 2, 1, 3]
my_list.sort()  # 오름차순으로 정렬
print(my_list)  # 출력: [1, 2, 3, 4]

my_list.sort(reverse=True)  # 내림차순으로 정렬
print(my_list)  # 출력: [4, 3, 2, 1]


my_list = [4, 2, 1, 3]
sorted_list = sorted(my_list) 
# 오름차순으로 정렬된 새로운 리스트 반환
print(sorted_list)  # 출력: [1, 2, 3, 4]

sorted_list = sorted(my_list, reverse=True)  
# 내림차순으로 정렬된 새로운 리스트 반환
print(sorted_list)  # 출력: [4, 3, 2, 1]