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)์ ๊ฐ์ง๊ณ ์๊ณ , ๊ฐ ๋์๋ ๋ฌด๊ฒ๊ฐ ์๋ค.
์ด ๋๋ค์ ๋ค์ ๊ท์น์ ๋ฐ๋ผ ํ๋ ๋๋ ์์ ๋๊น์ง ๋ถ๋ชํ ์์ ๋ ์๋ฎฌ๋ ์ด์
์ ํ๋ค:
๐จ ์๋ฎฌ๋ ์ด์ ๊ท์น
- ๋งค ๋จ๊ณ์์ ๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ๋ ๊ฐ์ ๋์ ์ ํํ๋ค. (x, y, ๋จ, x ≤ y)
- ๋ ๋์ ์๋ก ๋ถ๋ชํ๋ค:
- x == y → ๋ ๋ค ํ๊ดด๋จ (์ญ์ )
- x != y → ์์ ๋ x๋ ํ๊ดด๋๊ณ , ํฐ ๋ y๋ y - x ๋ฌด๊ฒ๋ก ๋ฐ๋
- ์ ๊ณผ์ ์ ๋์ด ํ๋ ์ดํ๋ก ๋จ์ ๋๊น์ง ๋ฐ๋ณตํ๋ค.
๐ฏ ์ต์ข ๋ชฉํ
๋์ด ๋ง์ง๋ง์ ํ๋ ๋จ์ผ๋ฉด ๊ทธ ๋์ ๋ฌด๊ฒ๋ฅผ ๋ฐํํ๊ณ ,
์๋ฌด๊ฒ๋ ์ ๋จ์ผ๋ฉด 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