leetcode.com 1046. Last Stone Weight

문제 링크: https://leetcode.com/problems/last-stone-weight/description/

파이썬 소스: https://bit.ly/3I5IUwl

 

heapq 와 PriorityQueue를 중 1가지를 사용해서 풀 수 있는 문제입니다.

속도 면에서는 heapq가 더 빠르겠지만, leetcode.com 703. Kth Largest Element in a Stream

문제를 풀 때, heapq를 사용해봤기 때문에, 이번문제 에서는 PriorityQueue 를 사용하겠습니다.

더 큰 값이 앞으로 오도록 하기 위해서 (self.max - stone, stone) 이렇게 튜플을

사용한 부분이 문제를 PriorityQueue를 사용해서 풀기위해 중요한 부분입니다.


from typing import List
from queue import PriorityQueue

class Solution:
    def __init__(self):
        self.max = 1000

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

        for stone in stones:
            pq.put((self.max - stone, stone))

        while pq.qsize() > 1:
            y = pq.get()[1]
            x = pq.get()[1]

            if x == y:
                continue
            elif x != y:
                n = y - x
                pq.put((self.max - n, n))

        if pq.qsize() >= 1:
            return pq.get()[1]

        return 0