[Leetcode / Python] 3066. Minimum Operations to Exceed Threshold Value II

난이도 : medium

 

리스트 nums와 숫자 k가 있을때,

nums에서 가장 작은 두 개의 숫자 x, y를 nums에서 제거하고, min(x, y)*2 + max(x, y)를 리스트에 넣는 계산을 반복

nums의 요소가 전부 k보다 클때까지 계산을 진행하는 횟수를 return하는 문제

 

import heapq

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        i = 0
        
        while nums[0] < k:
            s = heapq.heappop(nums)
            ss = heapq.heappop(nums)
            heapq.heappush(nums, s*2 + ss)
            i += 1
        return i

1. heapq를 가져오고, 리스트를 heapify한다. (heap 자료구조는 priority quere)
2. nums[0] (최소값)이 k보다 작을 때까지 while 계산
3. heapq.heappop으로 nums 내 가장 작은 값을 두번 뽑아냄(s : 제일 작은 수, ss : 두번째로 작은 수)
4. nums에 s*2 + ss를 nums에 추가
5. while이 몇 번 돌았는지를 세었던 i를 return

Runtime : 213ms (70.17%)

Memory : 35.33MB (91.60%)

 

 

참고로 이건 시간 제한에 걸린 방법이다.

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        i = 0
        nums = sorted(nums)
        while nums[0] < k:
            a = nums
            nums = sorted([a[0] * 2 + a[1]] + a[2:])
            i += 1
        return i