1046. Last Stone Weight

Last Stone Weight - LeetCode

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

참고 url 은 다음과 같다.

heapq - Heap queue algorithm