2023.04.25 Today's Challenge

fabichoi 2023. 4. 25. 23:45

https://leetcode.com/problems/last-stone-weight/

Last Stone Weight - LeetCode

Can you solve this real interview question? Last Stone Weight - You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them

leetcode.com

최대 힙으로 푸는 문제!

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        mh = [-stone for stone in stones]
        heapq.heapify(mh)

        while len(mh) > 1:
            stone1 = heapq.heappop(mh)
            stone2 = heapq.heappop(mh)

            if stone1 != stone2:
                heapq.heappush(mh, stone1 - stone2)
        
        if mh:
            return -mh[0]

        return 0