Final Array State After K Multiplication Operations I(Array,Math,Heap (Priority Queue),Simulation)

https://leetcode.com/problems/final-array-state-after-k-multiplication-operations-i/description/?envType=daily-question&envId=2024-12-16

You are given an integer array nums, an integer k, and an integer multiplier.

You need to perform k operations on nums. In each operation:

• Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
• Replace the selected minimum value x with x * multiplier.

Return an integer array denoting the final state of nums after performing all k operations.

 

Example 1:

Input: nums = [2,1,3,5,6], k = 5, multiplier = 2

Output: [8,4,6,5,6]

Explanation:

OperationResult

After operation 1	[2, 2, 3, 5, 6]
After operation 2	[4, 2, 3, 5, 6]
After operation 3	[4, 4, 3, 5, 6]
After operation 4	[4, 4, 6, 5, 6]
After operation 5	[8, 4, 6, 5, 6]

Example 2:

Input: nums = [1,2], k = 3, multiplier = 4

Output: [16,8]

Explanation:

OperationResult

After operation 1	[4, 2]
After operation 2	[4, 8]
After operation 3	[16, 8]

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 10
• 1 <= multiplier <= 5

Heap을 쓰는 문제라고 한다..

 

워밍업으로 한 번 풀어보자.

 

1. Python

Python은 Method가 많아서 얍삽이로 풀이가 가능하다.

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        for i in range(k):
            idx = nums.index(min(nums))
            nums[idx] *= multiplier
        return nums

 

 

Priority Queue로도 함 풀어볼까나?

 

C로 풀긴 좀 짜치니까 C++로 진행

 

 

3. C++

Priority queue에서 이렇게 customize로 크기 비교하는 container 만드는 방법 한 번쯤 정리가 필요하다.

CompareSecond 요기 부분이 Kick인 코드다.

 

struct CompareSecond{
    bool operator()(pair<int,int> const &c1,pair<int,int> const &c2){
        if(c1.second == c2.second) return c1.first > c2.first; // index control for same values
        return c1.second > c2.second;
    }
};

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,CompareSecond> pq;
        
        for(int i=0;i<nums.size();i++){
            pq.push({i,nums[i]});
        }
        
        for(int j=0;j<k;j++){
            pair<int,int> temp = pq.top();
            pq.pop();
            pq.push({temp.first,(temp.second)*multiplier});
        }
        int size = pq.size();
        for(int q=0;q<size;q++){
            pair<int,int> temp = pq.top();
            pq.pop();
            nums[temp.first] = temp.second;
        }
        return nums;
    }
};