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

 

난이도: 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. nums.

 

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

 

문제 예제

---

Example 1:

Input: nums = [2,11,10,1,3], k = 10
Output: 2
Explanation: In the first operation, we remove elements 1 and 2, then add 1 * 2 + 2 to nums. nums becomes equal to [4, 11, 10, 3].
In the second operation, we remove elements 3 and 4, then add 3 * 2 + 4 to nums. nums becomes equal to [10, 11, 10].
At this stage, all the elements of nums are greater than or equal to 10 so we can stop.
It can be shown that 2 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.

Example 2:

Input: nums = [1,1,2,4,9], k = 20
Output: 4
Explanation: After one operation, nums becomes equal to [2, 4, 9, 3].
After two operations, nums becomes equal to [7, 4, 9].
After three operations, nums becomes equal to [15, 9].
After four operations, nums becomes equal to [33].
At this stage, all the elements of nums are greater than 20 so we can stop.
It can be shown that 4 is the minimum number of operations needed so that all elements of the array are greater than or equal to 20.

 

제한 사항

---

• 2 <= nums.length <= 2 * 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109
• The input is generated such that an answer always exists. That is, there exists some sequence of operations after which all elements of the array are greater than or equal to k.

 

✏️ Solution(솔루션)

---

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        answer = 0

        while True:
            x = heapq.heappop(nums)
            if x >= k:
                break
            y = heapq.heappop(nums)
            heapq.heappush(nums, x * 2 + y)
            answer += 1

        return answer

 

이 문제는 nums에서 제일 작은 num(x)과 그 다음으로 작은 num(y)를 nums에서 빼주고, x * 2 + y 값을 다시 넣어주는 것을 반복하다가 nums의 요소가 모두 k 이상이면 종료하고 마지막에 반복 횟수를 반환하면 되는 문제였다.

 

나는 heapq를 이용해 문제를 해결했다.

 

처음에 nums를 heapq로 만들어 주었다.

 

그리고 while True문을 만들어 반복문을 만들었다.

 

반복문 안에서는 nums에서 heapop()을 통해 제일 작은 값(x)을 빼주었고, 이 제일 작은 값이 k보다 작다고 한다면 그 다음으로 작은 값(y)도 heappop()을 통해 빼주었다.

 

그리고 x * 2 + y의 결과 값을 다시 nums에 넣어주었고, answer도 +1 (반복 횟수) 해주었다.

 

만약 제일 작은 값이 k 이상이라고한다면 nums는 조건을 만족하기 때문에 break를 통해 빠져나왔다.

 

마지막으로 answer를 return하여 정답을 맞출 수 있었다.

 

---

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

 

깃허브: github

algorithmPractice/LeetCode/3332-minimum-operations-to-exceed-threshold-value-ii at main · laewonJeong/algorithmPractice