[LeetCode] 3066. Minimum Operations to Exceed Threshold Value II

https://leetcode.com/problems/minimum-operations-to-exceed-threshold-value-ii/description/

leetcode - Minimum Operations to Exceed Threshold Value II

문제 유형: 우선순위 큐, 힙, 그리디

문제 난이도: Medium

 

문제

You are given a 0-indexed integer array nums, and an integer k.

In one operation, you will:

• Take the two smallest integers x and y in nums.
• Remove x and y from nums.
• Add min(x, y) * 2 + max(x, y) anywhere in the array.

Note that you can only apply the described operation if nums contains at least two elements.

Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.

 

0-indexed의 정수 배열 nums와 정수 k가 주어집니다.

한 번의 연산에서, 당신은

• nums에서 가장 작은 두 수 x, y를 고릅니다.
• 그 두 수를 nums에서 없앱니다.
• nums의 어딘가에 min(x, y)*2 + max(x,y)를 추가합니다.

nums의 모든 요소가 k보다 크거나 같아지기 위한 최소 연산횟수를 구하시오.

정답이 구해지도록 보장됩니다.

 

풀이

최소 힙 우선순위 큐에 넣으면 쉽고 빠르게 가장 작은 수에 대해 조작할 수 있다.

pq의 top이 k보다 작은 동안, 먼저꺼낸 수를 x, 그 다음꺼낸 수를 y로 해서

x*2+y를 다시 pq에 넣으면 된다.

 

코드

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        priority_queue<long long, vector<long long>, greater<>> pq;
        for(const auto &num : nums) {
            pq.push(num);
        }

        int ans = 0;
        while(!pq.empty() && pq.top() < k) {
            long long x = pq.top(); pq.pop();
            long long y = pq.top(); pq.pop();

            pq.push(2*x+y);
            ans++;
        }

        return ans;
    }
};

 

Go

type MinHeap []int

func (h MinHeap) Len() int {return len(h)}
func (h MinHeap) Less(i, j int) bool {return h[i] < h[j]}
func (h MinHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i]} 

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func minOperations(nums []int, k int) int {
    h := &MinHeap{}
    heap.Init(h)

    for _, v := range nums {
        heap.Push(h, v)
    }

    ans := 0
    for h.Len() > 0 && (*h)[0] < k {
        x := heap.Pop(h)
        y := heap.Pop(h)

        heap.Push(h, x.(int)*2+y.(int))
        ans++
    }

    return ans
}