Heap-PrioiryQueue: 1046. Last Stone Weight

1046. Last Stone Weight

 

https://youtu.be/B-QCq79-Vfw?si=3xrwdkwlsVfUMrM8

 

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 기본적으로 minHeap 이니깐, -1 곱하면 maxheap 
        stones = [-s for s in stones]
        heapq.heapify(stones)
        print(stones)

        while len(stones) > 1:
            high_1st = heapq.heappop(stones)
            high_2nd = heapq.heappop(stones)

            if high_1st != high_2nd:
                heapq.heappush(stones, high_1st-high_2nd)

        #  stones 없으면, 0 추가되서, return stones[0], stones 있어도 상관 없음
        # stones.append(0) 
        return abs(stones[0]) if len(stones) == 1 else 0

 

최종 코드

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # 큰거 2개 선택해야하니, maxheap 으로
        # python 은 minheap 이 기본이니, 원래 값에서 -1 곱해서 maxheap 처럼
        mStones = [-1*s for s in stones]
        heapq.heapify(mStones)

        # 1개 남으면 그만둠
        while len(mStones) > 1:
            l1 = -1*mStones[0]
            heapq.heappop(mStones) 
            l2 = -1*mStones[0]
            heapq.heappop(mStones)

            if l1-l2 > 0:
                heapq.heappush(mStones, l2-l1)
        
        return -1*mStones[0] if len(mStones) > 0 else 0