Last Stone Weight

Q: Last Stone Weight의 시간 복잡도는 얼마인가요?

최대 힙을 사용하면 힙을 만들고 두 번의 pop과 한 번의 push를 수행하는 라운드를 최대 n-1 번 진행하는 데 O(n log n) 의 시간과 O(n) 의 공간이 걸립니다. 대신 매 라운드마다 전체 더미를 정렬하면 O(n² log n) 이 걸립니다.

쉬움힙

+10

돌무더기가 있고, stones[i]는 i번째 돌의 무게입니다. 매 라운드마다 가장 무거운 돌 두 개를 가져와 서로 부딪치게 합니다. 두 돌의 무게가 같으면 둘 다 부서집니다. 무게가 다르면 더 가벼운 돌은 부서지고, 더 무거운 돌의 무게는 두 무게의 차이만큼 줄어듭니다.

돌이 최대 하나만 남을 때까지 라운드를 진행하고, 남은 돌의 무게를 반환하거나 돌이 하나도 남지 않았으면 0을 반환하는 lastStoneWeight라는 함수를 작성하세요.

함수

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: 더미에 있는 돌들의 무게
반환값integer: 마지막 돌의 무게 또는 남은 돌이 없으면 0

제약 조건

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

예제

입력: stones = [3, 9, 4, 6, 2]
출력: 0
설명: 9와 6은 3을 남기고, 그다음 4와 3은 1을 남기며, 그다음 3과 2는 또 다른 1을 남깁니다. 무게가 1인 두 돌은 서로 파괴하므로 아무것도 남지 않고 답은 0입니다.

입력: stones = [10, 4, 1]
출력: 5
설명: 10과 4를 부수면 6이 남고, 6과 1을 부수면 5가 남습니다. 돌 하나가 남으며, 무게는 5입니다.

입력: stones = [8]
출력: 8
설명: 돌이 하나만 있으면 부딪쳐서 부술 것이 없으므로, 그 무게인 8이 정답입니다.

제출 시 숨은 테스트 +13개

후속 질문

무게는 최대 1000입니다. 이 상한을 이용해 힙 없이 O(n + W) 시간에 완료할 수 있을까요? 여기서 W는 가장 큰 무게입니다.

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

규칙은 시뮬레이션이므로 건너뛰는 공식이 없고, 모든 라운드를 진행해야 합니다. 각 라운드에서는 계속 바뀌는 더미에서 가장 무거운 돌 두 개를 찾아야 합니다. 돌을 부수면 더 가벼운 돌로 돌아올 수 있기 때문입니다. 매 라운드 다시 정렬하면 두 돌을 찾을 수 있지만 라운드마다 O(n log n)의 비용이 듭니다. 최대 힙을 사용하면 가장 무거운 돌을 꺼내고 새 돌을 다시 넣는 작업을 O(log n)에 할 수 있습니다.

매 라운드마다 더미를 정렬하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

규칙을 문자 그대로 따르세요. 가장 무거운 돌 두 개가 끝에 오도록 더미를 정렬하고, 두 돌을 꺼낸 다음 무게가 다르면 그 차이를 다시 넣으세요. 더미에 돌이 하나 또는 없을 때까지 반복하세요.

차이가 순서의 어느 위치에든 들어갈 수 있습니다. 첫 번째 예시에서는 9와 6의 차이로 3이 남는데, 이는 4보다 아래에 있어야 하므로 다음 라운드에서 가장 무거운 두 돌을 찾기 전에 다시 정렬해야 합니다.

매 라운드마다 돌이 적어도 하나 제거되므로 라운드 수는 최대 n-1이고, 각 라운드에서는 돌이 최대 n개인 더미를 정렬합니다. 따라서 시간 복잡도는 O(n² log n)입니다. n = 10^4이면 최대 10^4개의 숫자를 정렬하는 작업을 약 10^4번 해야 하므로, 정렬 과정에서 목록이 거의 정렬된 상태라는 점을 활용하더라도 최소 5 × 10^7번의 단계가 필요하고, 그렇지 않으면 그보다 몇 배 더 걸립니다. 이는 가장 큰 테스트 케이스를 처리하기에는 너무 느리지만, 아래의 힙은 몇십만 단계만 필요합니다.

알고리즘

돌들을 pile이라는 목록에 복사합니다.
더미에 돌이 두 개 이상 있는 동안 오름차순으로 정렬합니다.
마지막 두 돌인 heaviest와 second를 꺼냅니다.
두 돌의 무게가 다르면 heaviest - second를 더미에 다시 추가합니다.
남은 돌을 반환하거나, 더미가 비어 있으면 0을 반환합니다.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

최대 힙

핵심 아이디어

각 라운드에서는 가장 큰 돌만 필요하며, 전체 순서는 필요하지 않습니다. 이를 위해 최대 힙을 만듭니다. 최대 힙은 가장 큰 값을 맨 위에 유지하며, 맨 위 값을 제거하거나 값을 추가하는 데 O(log n)의 비용이 듭니다.

모든 돌을 힙에 넣습니다. 각 라운드마다 두 번 꺼내 가장 무거운 돌 두 개를 가져옵니다. 두 돌의 무게가 다르면 그 차이를 다시 넣습니다. 힙이 알아서 올바른 위치로 옮깁니다. [10, 4, 1]의 경우 10과 4를 꺼내 6을 넣고, 다음으로 6과 1을 꺼내 5를 넣으면 힙에는 5만 남습니다.

라운드는 최대 n-1번이며, 각 라운드마다 두 번 꺼내고 최대 한 번 넣으므로 시간 복잡도는 O(n log n)이고 힙은 O(n)의 공간을 사용합니다. 일부 언어는 힙을 기본 제공하는데, Python의 heapq는 최소 힙이므로 무게의 부호를 반대로 하여 저장합니다. Java에는 PriorityQueue, C++에는 priority_queue, Go에는 container/heap, Rust에는 BinaryHeap, PHP에는 SplMaxHeap이 있습니다. 그 밖의 언어에서는 배열로 직접 힙을 구현합니다. 인덱스 i의 부모는 (i-1)/2에 있으며, 새 값은 부모보다 우선순위가 높으면 위로 올라갑니다.

알고리즘

모든 돌을 최대 힙에 넣습니다.
힙에 돌이 두 개보다 많이 남아 있는 동안 가장 무거운 돌을 꺼낸 다음 두 번째로 무거운 돌을 꺼냅니다.
두 돌의 무게가 다르면 heaviest - second를 넣습니다.
힙이 비어 있으면 0을, 그렇지 않으면 힙의 맨 위 원소를 반환합니다.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

함정과 경계 사례

시뮬레이션은 짧지만, 버그는 끝부분과 힙 자체에 숨어 있습니다.

비어 있는 더미의 맨 위 값을 반환하는 경우. 마지막 두 돌의 무게가 같으면 남는 돌이 없으므로 답은 0입니다.
실수로 최소 힙을 사용하는 경우. Python의 heapq와 Java의 기본 PriorityQueue는 가장 작은 값을 꺼내므로, 무게를 음수로 바꾸거나 역순 비교자를 전달하세요.
다시 음수로 바꾸는 것을 잊는 경우. heapq에서는 꺼낸 값이 둘 다 음수이므로, 넣을 차이는 -(heaviest - second)입니다.
처음에 한 번만 정렬하고 목록을 따라가는 경우. 두 돌의 차이가 아직 건드리지 않은 돌보다 가벼울 수 있으므로, 고정된 순서는 첫 번째 라운드가 끝난 뒤에는 더 이상 유효하지 않습니다.

자주 묻는 질문4

Last Stone Weight의 시간 복잡도는 얼마인가요?

최대 힙을 사용하면 힙을 만들고 두 번의 pop과 한 번의 push를 수행하는 라운드를 최대 n-1번 진행하는 데 O(n log n)의 시간과 O(n)의 공간이 걸립니다. 대신 매 라운드마다 전체 더미를 정렬하면 O(n² log n)이 걸립니다.

Last Stone Weight에 힙을 사용하는 이유는 무엇인가요?

각 라운드에서는 매 라운드가 끝난 뒤 바뀌는 컬렉션에서 가장 큰 값 두 개를 찾습니다. 힙은 전체 컬렉션을 정렬된 상태로 유지하지 않고도 “가장 큰 값이 무엇인지” 알려 주며, 새 값을 O(log n)에 추가합니다. 시뮬레이션에서 반복하는 작업이 바로 이것입니다.

Last Stone Weight는 힙 없이 풀 수 있을까요?

네, 무게가 작기 때문입니다. 무게가 1부터 1000까지인 돌이 각각 몇 개 있는지 세고 가장 무거운 무게부터 내려가며 확인합니다. 무게가 같은 돌은 쌍으로 서로 상쇄되고, 새로 만들어지는 돌은 그 돌을 만드는 데 사용된 가장 무거운 돌보다 항상 가벼우므로, 확인 과정은 계속 아래로만 진행됩니다. 가장 큰 무게가 W일 때 실행 시간은 O(n + W)입니다.

같은 무게의 돌을 부수는 순서가 답을 바꾸나요?

아니요. 여러 돌의 무게가 가장 무거운 무게로 같다면, 어떤 두 개를 고르더라도 무게가 같으므로 한 라운드가 끝난 뒤 더미에 남는 무게도 같습니다. 답은 무게에만 달려 있으므로 모든 올바른 풀이가 같은 숫자를 반환합니다.

Python

def lastStoneWeight(stones):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

stones = [3, 9, 4, 6, 2]

기대값