[힙] 더 맵게 (Level 2)

1. 문제

2. 나의 풀이

2-1) 효율성을 통과하지 못한 나의 코드

def solution(scoville, K):
    count = 0
    target = 0
    scoville.sort()
    # print(scoville)
    count = 0
    while len(scoville) >= 2 and min(scoville) <= K:
        count += 1
        scoville.append(scoville.pop(0)+scoville.pop(0)*2)
        scoville.sort()
    
    if min(scoville) < K:
        return -1
    else:
        return count

2-2) heapq라는 자료구조를 이용해서 탈출!

import heapq

def solution(scoville, K):
    count = 0
    target = 0

    heap = []
    for i in scoville:
        heapq.heappush(heap,i)
    count = 0
    while len(heap) >= 2 and heap[0] <= K:
        count += 1
        heapq.heappush(heap, (heapq.heappop(heap) + heapq.heappop(heap) * 2))

    if heapq.heappop(heap) < K:
        return -1
    else:
        return count

3. 남의 풀이

Reference

• 파이썬 heapQ 사용법 (https://www.daleseo.com/python-heapq/)

4. 느낀 점

• heap을 이용해서 풀어야하는 문제!