[Neetcode/Heap] Last Stone Weight

https://neetcode.io/problems/last-stone-weight

NeetCode

🧩 문제 요약

당신은 여러 개의 돌(stone)을 가지고 있고, 각 돌에는 무게가 있다.
이 돌들을 다음 규칙에 따라 하나 또는 없을 때까지 부딪혀 없애는 시뮬레이션을 한다:

🔨 시뮬레이션 규칙

1. 매 단계에서 가장 무거운 두 개의 돌을 선택한다. (x, y, 단, x ≤ y)
2. 두 돌을 서로 부딪힌다:
   • x == y → 둘 다 파괴됨 (삭제)
   • x != y → 작은 돌 x는 파괴되고, 큰 돌 y는 y - x 무게로 바뀜
3. 위 과정을 돌이 하나 이하로 남을 때까지 반복한다.

🎯 최종 목표

돌이 마지막에 하나 남으면 그 돌의 무게를 반환하고,
아무것도 안 남으면 0을 반환한다.

🔍 예제 설명

예제 1:

Input: stones = [2, 3, 6, 2, 4]

Input: stones = [2, 3, 6, 2, 4]

• 6과 4 → 부딪혀서 6 - 4 = 2 → [2, 3, 2, 2]
• 3과 2 → 부딪혀서 3 - 2 = 1 → [1, 2, 2]
• 2와 2 → 같으므로 둘 다 제거 → [1]
• ✅ 남은 돌: 1

예제 2:

Input: stones = [1, 2]

• 2와 1 → 부딪혀서 2 - 1 = 1 → [1]
• ✅ 남은 돌: 1

💡 구현 팁

가장 무거운 두 개를 빠르게 꺼내기 위해 Max Heap을 사용하면 좋다.
하지만 Python의 heapq는 min heap만 제공하므로,
-무게를 넣어서 최대 힙처럼 동작하게 만들 수 있다.

 

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # Use a max heap by negating the values
        max_heap = [-stone for stone in stones]
        heapq.heapify(max_heap)  # Turn the list into a heap

        while len(max_heap) > 1: # Keep picking the two heaviest stones and smashing them
            # Pop two largest stones (remember to negate again)
            stone1 = -heapq.heappop(max_heap)
            stone2 = -heapq.heappop(max_heap)

            if stone1 != stone2:
                # If stones are not equal, push the remaining piece back into the heap
                heapq.heappush(max_heap, -(stone1 - stone2))

        # If there's one stone left, return it (negated back to positive)
        # Otherwise, return 0
        return -max_heap[0] if max_heap else 0