a-065-last-stone-weight2026-07-17easyleetcode #1046neetcode150

마지막 돌의 무게

#array#heap-priority-queue

↗ leetcode #1046 · a-065-last-stone-weight

문제

· problem

P.a-065-last-stone-weight

마지막 돌의 무게

정수 배열 stones가 주어지며, stones[i]는 i번째 돌의 무게입니다. 돌들로 게임을 합니다. 매 차례마다 가장 무거운 두 돌을 선택하여 함께 부습니다. 가장 무거운 두 돌의 무게를 x와 y라 하고 x ≤ y라고 가정합니다. 부딪침의 결과는: x == y이면 두 돌 모두 파괴됩니다. x != y이면 무게 x인 돌은 파괴되고, 무게 y인 돌의 새로운 무게는 y - x가 됩니다. 게임이 끝날 때 최대 한 개의 돌이 남습니다. 마지막에 남은 돌의 무게를 반환하세요. 남은 돌이 없으면 0을 반환하세요.

제약

· 1 ≤ stones.length ≤ 30
· 1 ≤ stones[i] ≤ 1000

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[2,7,4,1,8,1]

example 2input → output

[1]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
가장 무거운 두 돌이 같은 무게라면?
☐
배열을 원본 그대로 수정해야 하나요, 아니면 복사본을 만들어야 하나요?
☐
돌이 1개만 있으면 어떻게 되나요?
☐
가장 무거운 두 돌을 매번 찾을 때, 최대 얼마나 효율적으로 할 수 있을까요?
☐
파괴되는 돌들이 무엇인지 추적해야 하나요?
☐
돌을 부스르는 순서가 다르면 최종 결과가 달라질까요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 모든 돌을 음수로 변환

○

stones = [-s for s in stones]

○

stones.sort(reverse=True)

○

stones = [s for s in stones]

step 2· 배열을 힙 구조로 정렬

○

heapq.heapify(stones)

○

heapq.heapify(stones, key=lambda x: x)

○

stones = sorted(stones)

step 3· 두 개 이상의 돌이 남은 동안 반복

○

while len(stones) > 1:

○

while len(stones) > 0:

○

while stones:

step 4· 가장 무거운 돌 추출 (가장 음수)│ 중첩

○

first = heapq.heappop(stones)

○

first = stones[0]

○

first = max(stones) if stones else 0

step 5· 두 번째로 무거운 돌 추출│ 중첩

○

second = heapq.heappop(stones)

○

second = stones[0]

○

second = heapq.heappop(stones) or 0

step 6· 다르면 차이를 힙에 삽입│ 중첩

○

heapq.heappush(stones, first - second)

○

heapq.heappush(stones, second - first)

○

heapq.heappush(stones, abs(first - second))

step 7· 마지막 돌의 무게 반환

○

return abs(stones[0])

○

return stones[0]

○

return stones[0] if stones else 0

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

    def lastStoneWeight(self, stones: List[int]) -> int:

        stones = [-s for s in stones]

        heapq.heapify(stones)

        while len(stones) > 1:

            first = heapq.heappop(stones)

            second = heapq.heappop(stones)

            if second > first:

                heapq.heappush(stones, first - second)

        stones.append(0)

        return abs(stones[0])

# There's a private _heapify_max method.

# https://github.com/python/cpython/blob/1170d5a292b46f754cd29c245a040f1602f70301/Lib/heapq.py#L198

class Solution(object):

    def lastStoneWeight(self, stones):

        heapq._heapify_max(stones)

        while len(stones) > 1:

            max_stone = heapq._heappop_max(stones)

            diff = max_stone - stones[0]

            if diff:

                heapq._heapreplace_max(stones, diff)

            else:

                heapq._heappop_max(stones)

        stones.append(0)

        return stones[0]

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[2,7,4,1,8,1]

→

case 2

[1]

→

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.