본문 바로가기
CS/Algorithm

힙 > 더 맵게

by KJY 2021. 4. 4.

문제

코딩테스트 연습 - 더 맵게

풀이

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

댓글