[LeetCode] 3264. Final Array State After K Multiplication Operations I (Python)

 

난이도: Easy

 

문제 설명

---

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:

Operation	Result
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:

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

 

제한 사항

---

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

 

✏️ Solution(솔루션)

---

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        hq = [(num, i) for i, num in enumerate(nums)]
        heapq.heapify(hq)

        for _ in range(k):
            num, idx = heapq.heappop(hq)
            heapq.heappush(hq, (num*multiplier, idx))
            nums[idx] *= multiplier
        
        return nums

 

이 문제는 nums에서 제일 작은 요소를 multiplier 값으로 곱해 저장하고, 이러한 작업을 k번 반복하면 되는 문제였다.

 

이 문제 역시 heapq를 사용해 해결하였다.

 

먼저 nums의 각 요소와 각 idx를 튜플로 만들고 이를 heapq로 만들었다. ex) [1, 2, 3] => [(1, 0), (2, 1), (3, 2)]

 

그 후, k번 동안 heapq에서 제일 작은 요소를 pop했고, 그 과정에서 얻은 요소와 idx를 가지고 (num*multiplier, idx)를 heapq에 추가했다. 그리고 원래 nums[idx] *= multiplier를 해줌으로써 결과를 저장해 나갔다.

 

모든 연산을 끝마치면 nums를 그대로 return하여 정답을 맞출 수 있었다.

---

[LeetCode] 3264. Final Array State After K Multiplication Operations I