Last Stone Weight(Array,Heap (Priority Queue))

https://leetcode.com/problems/last-stone-weight/description/

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and
• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

 

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation: 
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

 

Constraints:

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

이전에 함 풀었던 문제이다. 과연 다시봐도 낭낭하게 풀 수 있는지 체크해보자.

 

1. Python

핵 조잡하게 완

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        while len(stones) > 1 :
            stones = sorted(stones)
            top1 = stones.pop() 
            top2 = stones.pop() 
            if top1 == top2 : continue
            else :
                top1 -= top2
                stones.append(top1)

        if len(stones) == 0 : return 0
        else : return stones[0]

코드를 조잡하게 짰는데 효율이 좋다는게 이상하다;;

2. C++

명색이 Heap 문제인데 C++ heap 구조를 이용해서 풀어보자.

 

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for(int x : stones){
            pq.push(x);
        }

        while(pq.size()>1){
            int a = pq.top();
            pq.pop();
            int b = pq.top();
            pq.pop();
            if(a==b) continue;
            else pq.push(a-b);
        }
        if(pq.empty()) return 0;
        else return pq.top();
    }
};

 

참고로 아래처럼 pq를 vector내용 한 번에 넣어서 초기화 할 수 도 있고,

return 값을 삼항연산자(Ternary Operator)를 써서 좀 깔롱지게 표현가능하다.

 

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(),stones.end());

        while(pq.size()>1){
            int a = pq.top();
            pq.pop();
            int b = pq.top();
            pq.pop();
            if(a==b) continue;
            else pq.push(a-b);
        }
        return pq.empty() ? 0 : pq.top();
    }
};