🚀 1046. 마지막 돌의 무게

마지막 돌의 무게

Last Stone Weight - LeetCode

문제 설명

정수 배열 stones가 주어지며, stones[i]는 i번째 돌의 무게를 나타냅니다.

우리는 돌을 가지고 게임을 합니다. 매 턴마다 가장 무거운 두 개의 돌을 선택하여 서로 부딪힙니다. x와 y를 각각 두 돌의 무게라고 할 때 (x ≤ y), 부딪힌 결과는 다음과 같습니다:

• 만약 x == y라면, 두 돌 모두 파괴됩니다.
• 만약 x != y라면, x 무게의 돌은 파괴되고, y 무게의 돌은 y - x의 새로운 무게를 갖게 됩니다.

게임이 끝날 때는 최대 한 개의 돌만 남게 됩니다.

마지막에 남은 돌의 무게를 반환하세요. 남은 돌이 없다면 0을 반환하세요.

예제 1:

입력: stones = [2,7,4,1,8,1]
출력: 1
설명: 
7과 8을 부딪혀서 1이 되어 배열은 [2,4,1,1,1]이 됩니다.
2와 4를 부딪혀서 2가 되어 배열은 [2,1,1,1]이 됩니다.
2와 1을 부딪혀서 1이 되어 배열은 [1,1,1]이 됩니다.
1과 1을 부딪혀서 0이 되어 배열은 [1]이 되고, 이것이 마지막 돌의 무게입니다.

예제 2:

입력: stones [1]
출력: 1

제약 조건:

- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000

해결 방법

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while stones and stones[-1]:
            stones = heapq.nsmallest(len(stones), stones)
            if len(stones) == 1:
                return stones.pop()
            elif len(stones) == 2:
                return stones.pop() - stones.pop()
            item1 = stones.pop()
            item2 = stones.pop()
            if item1 - item2 is not 0:
                stones.append(item1 - item2)

결과 runtime : 30ms 96.20%

근데 이렇게 사용하는거면 그냥 sort쓰는게 맞지 않나 생각?

다른 사람들은 어떻게 풀었나 확인해보니

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones = [-stone for stone in stones]
        heapq.heapify(stones)
        while len(stones) > 1:
            y = heapq.heappop(stones)
            x = heapq.heappop(stones)
            if x != y:
                heapq.heappush(stones, y - x)
        return -stones[0] if stones else 0

다른 사람들이 푼 결과는 이렇다.

그러니까 heapq는 모듈이고 그걸 그대로 활용하는데 요소들의 값을 다 마이너스로 바꾸고 마이너스로 바뀐 요소를 힙 정렬해버리면 큰수대로 이진트리로 정렬되고 최종 결과에 -만 붙여서 반영하면 됨

설명

이 해결방법은 Python의 heapq 모듈을 사용합니다:

1. 모든 돌의 무게를 음수로 변환합니다 (최대 힙을 구현하기 위해)
2. heapify를 사용하여 힙으로 변환합니다
3. 돌이 2개 이상 남아있는 동안:
   • 가장 큰 두 돌을 꺼냅니다 (음수이므로 실제로는 가장 작은 값)
   • 두 돌의 차이가 있다면 새로운 돌을 힙에 추가합니다
4. 마지막 돌이 남아있다면 그 값을 양수로 변환하여 반환하고, 없다면 0을 반환합니다

참고 url 은 다음과 같다.

참고 자료

heapq - Heap queue algorithm