문제
풀이
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
L = len(scoville)
min_k = heapq.heappop(scoville)
for i in range(1, L):
second_k = heapq.heappop(scoville)
min_k = heapq.heappushpop(scoville, min_k + (second_k * 2))
if min_k >= K:
return i
return -1
속도
min : 통과 (0.01ms, 10.2MB)
max : 통과 (2129.86ms, 51.9MB)
다른 풀이
heap 사용 → import heapq
heapq 만들기 → heapq.heapify()
heap 넣기 → heapq.heappush()
heap 넣고 빼기 → heapq.heappushpop([], 넣을거)
heap 빼기 → heapq.heappop()
최대힙 만들기
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))
튜플을 넣으면 첫번째 원소를 기준으로 집어 넣음 → 밴대로 넣게 되는 것임 → 최대힙 구현
'CS > Algorithm' 카테고리의 다른 글
백준 9093 (0) | 2021.05.17 |
---|---|
백준 9012번 (0) | 2021.05.17 |
해시 > 전화번호 목록 (0) | 2021.04.04 |
스택 > 다리를 지나는 트럭 (0) | 2021.03.28 |
해시> 완주하지 못한 선수 (0) | 2021.03.28 |
댓글