IT/Computer Science

[Neetcode/Heap] Last Stone Weight

Diana Kang 2025. 4. 11. 22:42

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

 

NeetCode

 

neetcode.io

๐Ÿงฉ ๋ฌธ์ œ ์š”์•ฝ

๋‹น์‹ ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋Œ(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