[Leetcode 1046] - Last Stone Weight w/ Python

 

 

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 together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is: 

 

If x == y, both stones are destroyed, and 

If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. 

 

At the end of the game, there is at most one stone left. Return the weight of the last remaining stone. If there are no stones left, return 0.

 

 

 

돌의 무게가 들어있는 배열이 주어진다. 이 배열에서 가장 무거운 돌 2개를 꺼내

서로 부딛혀 서로의 값만큼 무게가 감소한다.

 

돌의 무게가 같다면 둘다 파괴, 한개가 더 크다면 더 작은 무게의 돌이 파괴되고

큰 무게는 작은 무게만큼 무게값이 감소한다

 

한개의 돌이 남았을때 그 돌의 무게를 리턴

만약 돌이 한개도 안남는다면 0을 리턴하는 문제

 

 

 

 

 

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

 

 

 

---

 

 

 

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

 

 

 

Example 2:

Input: stones = [1]
Output: 1

 

 

 

---

 

 

 

돌의 무게중 가장 큰 두개를 사용해야되고, 정렬을 하기엔 너무

시간이 오래 걸려 heapq를 사용하게 되었다

 

이때 heap에 추가할때 음수로 만들어서 최대값을 찾고,

부딛힌 돌의 값을 heap으로 다시 저장한다

 

이때 가장 마지막으로 남은 값을 리턴한다

 

 

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = []
        for stone in stones:
            heapq.heappush(heap, -stone)
        
        while len(heap) > 1:
            x = heapq.heappop(heap)
            y = heapq.heappop(heap)
            stone = x - y
            heapq.heappush(heap, stone)
        
        return -heap[0]