[힙(Heap)] 더 맵게

힙(Heap) - 더 맵게

간단하게 파이썬의 힙을 이용했다. 파이썬의 heapq 모듈은 최소 힙으로만 구현되어 있는데, 이 문제는 최소 힙을 활용하면 되는 거라 간단히 풀이가 가능했다.
여전히 분기를 깔끔하게 잘 하는 건 노력이 필요할 것 같다.

import heapq

def solution(scoville, K):

    answer = 0
    heapq.heapify(scoville)

    while (scoville):

        min1 = heapq.heappop(scoville)

        if min1 >= K: return answer
        if not scoville: break
        else:
            min2 = heapq.heappop(scoville)
            temp = min1+min2*2
            heapq.heappush(scoville, temp)
            answer += 1

    return -1

• 시간 초과가 나는 단순 정렬 풀이
  단순히 매번 전체 리스트를 정렬하는 것과 달리 힙은 삽입과 삭제를 하면서 항상 자료 구조를 유지하기 위한 동작을 수행한다. 이 때의 시간 복잡도는 O(log n)이 소요된다.
  힙 구조를 이용해서 삽입/삭제를 수행하는 것이 속도 측면에서 훨씬 효율적일 수 밖에 없을 것이다.

def solution(scoville, K): 
    answer = 0

    while (scoville):
        scoville.sort(reverse=True)     
        min1 = scoville.pop()

        if min1 >= K: return answer
        if not scoville: break
        else:
            min2 = scoville.pop()
            temp = min1+min2*2
            scoville.append(temp)
            answer += 1

    return -1