농심 라면 공장
배열에 새로운 값이 계속 들어오는데, 최대값이나 최소값이 필요하다면 heap을 쓰는것이 좋다.
heap은 최대값과 최소값을 자동으로 계속 만들어주는 자료구조이기 때문!
- 파이썬에서 heap은
import heapq로 사용한다. - heap의 최소값은 heap의 [0]번째 인덱스이고 최대값은 값을 넣을때 (heappush) 마이너스 값으로 넣고 [0]번째 값을 리턴할때 다시 마이너스를 붙여주면 된다. 꿀팁...!
>>> import heapq # heapq 를 사용하기 위해서 임포트.
>>> heap = []
>>> heapq.heappush(heap, 4 * -1)
>>> heapq.heappush(heap, 1 * -1)
>>> heapq.heappush(heap, 7 * -1)
>>> heapq.heappush(heap, 3 * -1)
>>> print(heap)
[-7, -3, -4, -1] # 힙의 형태를 유지한채로 원소가 넣어지기 때문에 heap[0]이 최소값!
>>> print(heapq.heappop(heap) * - 1) # 최대값을 빼는 방법.
7
>>> print(heap)
[-4, -3, -1] # 마찬가지로 힙의 형태가 유지됨.
import heapq
ramen_stock = 4
supply_dates = [4, 10, 15, 20]
supply_supplies = [20, 5, 10, 5]
supply_recover_k = 40
def get_minimum_count_of_overseas_supply(stock, dates, supplies, k):
result = 0
heap = []
i = 0
while k > stock: # k와 stock이 같을때엔 딱 맞아떨어지므로 밀가루를 더 가져오지 않아도 된다.
while i < len(dates) and dates[i] <= stock: # dates는 순차정렬되어있고, 공급이 불가능한 경우는 매개변수에 받지않는다고 가정한다.
heapq.heappush(heap, -1 * supplies[i])
i += 1
result += 1
stock += -1 * heapq.heappop(heap)
return result
print(get_minimum_count_of_overseas_supply(ramen_stock, supply_dates, supply_supplies, supply_recover_k))** 문제 내에 주석과 같은 오류가 조금 있음.
빠굥