[Leetcode] 1046. Last Stone Weight 문제 풀이

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

Last Stone Weight - LeetCode

문제 내용

각 돌에 weight가 있고 2개의 돌이 부딫히면 weight 가 차이만큼 줄어드는 돌이 하나가 생긴다.

최종적으로 1개가 남을 때 까지 계속 할 때 최소 weight 구하는 문제

만약 하나도 남지 않으면 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

문제 풀이

돌맹이 2개를 선택해서 그 차이가 가장 작게 만들어야한다.

차이를 가장 작게 만드는 방법 중에 제일 큰 수 2개를 선택하는 방법이 있다.

제일 큰 수 2개를 선택하면 다른 선택을 하는 것 보다 차이가 작다는 것을 보장할 수 있다.

가장 큰 수를 선택하는 자료구조로 max heap을 사용하면 된다.

 

코드

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue max_heap {stones.begin(), stones.end()};
        
        while (max_heap.size() > 1) {
            auto a = max_heap.top();
            max_heap.pop();
            
            auto b = max_heap.top();
            max_heap.pop();
            
            int d = abs(a - b);
            if (d)
                max_heap.push(d);
        }
        
        return max_heap.size() == 0 ? 0 : max_heap.top();
    }
};