[LeedCode] 1167. Minimum Cost to Connect Sticks 파이썬 Medium

문제 해석:

주어진 양의 정수 리스트에서 두개의 숫자를 뽑아 하나의 막대로 연결해야한다.
하나의 막대를 연결하는 비용은 각 막대의 값의 합과 같다.
모든 막대를 연결했을때 가장 최소비용은 얼마인가?

문제 해설:

1. 최소비용을 구하기 위해서는 가장 작은 막대들부터 연결해야한다.
2. 막대들 중에 작은 숫자를 순서대로 꺼내서 연산해야하기 때문에, Priority Queue, Heap을 사용할 수 있다.
(자료구조를 사용하지 않고, 매번 정렬하면 시간이 오래걸린다.)
3. 힙에서 두개의 숫자를 꺼내, 합하고 그비용을 결과에 더한다.
4. 그리고 연결되어 생성된 막대를 다시 힙에 넣는다.
5. 위의 과정을 막대가 1개가 될때까지 반복한다.

1167. Minimum Cost to Connect Sticks

You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.

You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

 

Example 1:

Input: sticks = [2,4,3] Output: 14 Explanation: You start with sticks = [2,4,3]. 1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4]. 2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9]. There is only one stick left, so you are done. The total cost is 5 + 9 = 14.

Example 2:

Input: sticks = [1,8,3,5] Output: 30 Explanation: You start with sticks = [1,8,3,5]. 1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5]. 2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8]. 3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17]. There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.

Example 3:

Input: sticks = [5] Output: 0 Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

 

Constraints:

• 1 <= sticks.length <= 104
• 1 <= sticks[i] <= 104

소스코드:

Heap

# 힙 풀이
class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        heapq.heapify(sticks)
        res = 0
        while len(sticks) > 1:
            v1 = heapq.heappop(sticks)
            v2 = heapq.heappop(sticks)
            res += (v1 + v2)
            heapq.heappush(sticks, v1 + v2)
        return res

Priority Queue

from queue import PriorityQueue
class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        pq = PriorityQueue()
        res = 0
        for i in sticks:
            pq.put(i)
        while pq.qsize() > 1:
            v1 = pq.get()
            v2 = pq.get()
            sv = v1 + v2
            res += sv
            pq.put(sv)
        return res

정렬

class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        stickSize = len(sticks)
        if stickSize <= 1:
            return 0
        sumV = 0
        li = sticks
        for i in range(stickSize - 1):
            li = sorted(li, reverse=True) # 4 3 2
            val1 = li.pop()
            val2 = li.pop()
            tmp = val1 + val2
            sumV += tmp
            li.append(tmp)
        return sumV