leetcode) 330. Patching Array

330. Patching Array

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        ans, total, idx = 0, 0, 0
        while total < n:
            if idx < len(nums):
                if total < nums[idx] - 1:
                    total = total * 2 + 1
                    ans += 1
                else:
                    total += nums[idx]
                    idx += 1  
            else:
                total = total * 2 + 1
                ans += 1
        
        return ans

풀이

전제

1. 가지고 있는 숫자로 m까지의 숫자를 만들 수 있다고 한다면 2 * m + 1 까지의 숫자를 만들때 필요한 숫자는 하나이다.
2. 그리고 m까지의 숫자를 만들 수 있지만 m보다 작은 k라는 숫자를 하나 더 가지게 되면 m + k까지의 숫자를 만들 수 있게 된다.

해설

1. total은 만들 수 있는 최대 값을 저장합니다. idx로 진행하면서 각 숫자를 total에 더하면서 진행 합니다. 숫자를 더할 필요가 있을 때 ans에 숫자를 더하여 줍니다.
2. 기본적으로 idx > len(nums)인 상황에서는 계속 해서 새로운 숫자를 만들어 주어야 합니다.
3. idx < len(nums) 인 상황에서는 일단 total에 만들 수 있는 최대 값을 저장합니다.
   1. total과 nums[idx]-1을 비교하여 total이 크거나 같은 경우는 이미 nums[idx]보다 크거나 같은 값을 만들 수 있기 때문에 total을 total+ nums[idx]로 재조종하고 다음 idx로 넘어갑니다.
   2. total과 nums[idx]-1을 비교하여 total이 작은 경우는 숫자를 더 필요로 하기 때문에 숫자를 하나 더 만들고 total을 total * 2 + 1로 재조정하고 ans도 1 더 해줍니다. 정확히 필요한 숫자는 total+1입니다. (하지만 문제를 풀때는 필요가 없습니다.)
4. 이런 식으로 반복하여서 만들 수 있는 가장 큰 수 인 total이 n보다 크거나 같을 때까지 반복하면 됩니다.