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

Problem

 

Solution

heap

nums에서 k보다 작고 가장 작은 최소값 2개를 구해서 min(x,y) * 2 + max(x,y) 를 nums에 추가한다.

이때 최소값 2개는 반드시 필요하다.

위 반복 작업을 몇 번하는지 카운트하는 문제.

 

 

Code

import heapq

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

        while(len(nums) > 1 and nums[0] < k):
            num1 = heapq.heappop(nums)
            num2 = heapq.heappop(nums)
            newNum = num1 * 2 + num2
            heapq.heappush(nums, newNum)

            answer += 1

        return answer

 

Complexity

Time Complexity

heapq.heapify(nums) -> O(N)

 

num1 = heapq.heappop(nums) # O(log N)

num2 = heapq.heappop(nums) # O(log N)

newNum = num1 * 2 + num2 # O(1)

heapq.heappush(nums, newNum) # O(log N)

 

O(longN) 연산을 N 번 반복하므로 최종적으로 O(NlogN) 시간 복잡도가 소요된다.

 

Space Complexity

heap에서 연산을 하므로 O(N)