[LeetCode] 1167. Minimum Cost to Connect Sticks

 integer로 구성된 sticks라는 input array의 모든 요소를 이어 붙이는 문제다. 이 때 더할 때 마다 발생하는 합이 최소가 되도록 하는 문제다. sorting을 통해 풀이를 해야하나 잠시 생각했지만 Min heap을 사용하면 쉽게 구현이 가능하다.

 

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        mh = sticks
        ret = 0

        heapify(mh)

        while len(mh) > 1:
            m1 = heappop(mh)
            m2 = heappop(mh)
            sum_ = m1 + m2
            ret += sum_
            heappush(mh, sum_)

        return ret