Last Stone Weight
돌무더기가 있고, stones[i]는 i번째 돌의 무게입니다. 매 라운드마다 가장 무거운 돌 두 개를 가져와 서로 부딪치게 합니다. 두 돌의 무게가 같으면 둘 다 부서집니다. 그렇지 않으면 더 가벼운 돌은 부서지고, 더 무거운 돌의 무게는 두 무게의 차이만큼 줄어듭니다.
돌이 최대 하나 남을 때까지 라운드를 진행하고 남은 돌의 무게를 반환하거나, 돌이 하나도 남지 않았을 때 0을 반환하는 lastStoneWeight를 작성하세요.
함수
- stonesinteger-array
- 더미에 있는 돌의 무게
- 반환값integer
- 마지막 돌의 무게 또는 남은 돌이 없으면 0
제약 조건
1 ≤ stones.length ≤ 1041 ≤ 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이 답입니다.
후속 질문
무게는 최대 1000입니다. 이 상한을 활용해 힙 없이 O(n + W) 시간에 끝낼 수 있나요? 여기서 W는 가장 큰 무게입니다.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
설명된 대로 라운드를 진행하세요. 매 라운드가 시작될 때 무엇을 빠르게 찾아야 하나요?
매 라운드마다 가장 무거운 돌 두 개가 필요하며, 다시 넣는 돌은 이미 더미에 있는 돌보다 가벼울 수 있습니다. 새로운 값이 들어온 후에도 항상 가장 큰 값을 알고 있는 자료 구조를 사용하면 다시 정렬하지 않아도 됩니다.
모든 돌을 최대 힙에 넣습니다. 두 번 꺼내고, 차이가 0이 아니면 그 차이를 넣은 다음 돌이 하나 이하로 남을 때까지 반복합니다. 남은 돌을 반환하거나
0을 반환합니다.
풀이
건너뛰기 위한 공식은 없습니다. 모든 라운드를 플레이해야 합니다. 부서진 돌이 더 가벼운 무게로 다시 돌아올 수 있으므로, 각 라운드마다 계속 바뀌는 더미에서 가장 무거운 돌 두 개가 필요합니다. 최대 힙은 가장 무거운 돌을 꺼내고 새 돌을 다시 넣는 작업을 O(log n)에 처리합니다.
매 라운드마다 더미를 정렬합니다
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
규칙을 그대로 따르세요. 돌무더기를 정렬하고, 끝에서 가장 무거운 돌 두 개를 꺼내 그 차이가 0이 아니면 다시 넣습니다. 차이는 어디에든 들어갈 수 있으므로 매 라운드마다 다시 정렬하세요. 첫 번째 예시에서 9와 6을 꺼내면 3이 남고, 이는 4보다 아래에 놓입니다.
매 라운드마다 돌이 적어도 하나 제거되므로 라운드는 최대 n-1회이고, 각 라운드마다 최대 n개의 돌을 정렬합니다. 따라서 시간 복잡도는 O(n² log n)입니다. n = 10^4일 때 최대 10^4개의 숫자를 정렬하는 작업을 약 10^4회 수행합니다.
알고리즘
- 돌들을
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)의 비용이 듭니다. 모든 돌을 힙에 넣으세요. 각 라운드마다 가장 무거운 돌 두 개를 꺼내고, 차이가 0이 아니면 그 차이를 다시 넣으세요. 힙이 값을 올바른 위치로 이동시킵니다. [10, 4, 1]의 경우 10과 4를 꺼내고 6을 넣은 다음, 6과 1을 꺼내고 5를 넣습니다.
두 번 꺼내고 한 번 넣는 라운드는 최대 n-1번이므로, 시간 복잡도는 O(n log n)이고 공간 복잡도는 O(n)입니다. 내장 힙이 없는 언어에서는 배열로 힙을 구현하며, 인덱스 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는 가장 작은 값을 꺼냅니다. 무게에 음수를 취하거나 역순 비교기를 전달하세요. - 음수로 바꾼 무게의 부호를 잊는 경우. 꺼낸 값은 둘 다 음수이므로, 추가할 값은
-(heaviest - second)입니다. - 처음에 한 번 정렬한 뒤 목록을 순회하는 경우. 차이는 아직 다루지 않은 돌보다 가벼울 수 있으므로, 첫 번째 라운드가 끝나면 순서가 더 이상 유효하지 않습니다.
자주 묻는 질문3
Last Stone Weight의 시간 복잡도는 얼마인가요?
최대 힙을 사용하면, 두 번의 pop과 한 번의 push를 수행하는 최대 n-1라운드에 O(n log n) 시간이 걸리고 O(n) 공간이 필요합니다. 매 라운드마다 전체 더미를 정렬하면 O(n² log n) 시간이 걸립니다.
Last Stone Weight에 정렬된 목록 대신 힙을 사용하는 이유는 무엇인가요?
정렬된 목록에서는 가장 무거운 돌 두 개를 한 번에 확인할 수 있지만, 차이를 다시 제자리에 넣으려면 최대 n개의 항목을 이동해야 하므로 모든 라운드를 통틀어 O(n²)의 시간이 걸립니다. 힙은 "가장 큰 값이 무엇인지"만 알려 주고 새 값을 추가하며, 이 두 작업 모두 O(log n)에 수행되는데, 시뮬레이션에 필요한 것은 이뿐입니다.
무게가 같은 돌을 부수는 순서가 답을 바꾸나요?
아니요. 여러 돌의 무게가 가장 무겁게 같다면 어느 것을 고르든 두 돌의 무게는 같으므로, 한 라운드가 끝난 뒤 더미에 남는 돌의 무게도 같습니다. 답은 무게에만 달려 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def lastStoneWeight(stones):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
stones = [3, 9, 4, 6, 2]
예상 출력
0