[2024] day 169. Leetcode 330. Patching Array

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 16일 (일)
Leetcode daily problem

330. Patching Array

https://leetcode.com/problems/patching-array/?envType=daily-question&envId=2024-06-16

Problem

정렬된 정수 배열 nums 및 정수 n이 주어지면 [1, n] 범위의 모든 숫자가 배열의 일부 요소의 합으로 형성될 수 있도록 배열에 요소를 추가/패치 한다. 여기서 필요한 최소 패치 수를 반환한다.

Solution

?

주어진 배열 nums에 최소한의 패치를 추가해 1부터 n까지 모든 숫자를 만들 수 있도록 해야 하는데, 현재까지 만들 수 있는 가장 큰 범위를 유지하는 것이 포인트이다.

현재까지 만들 수 없는 가장 작은 숫자(miss)를 초기값으로 1을 두고, 추가한 패치 숫자와 주어진 nums의 배열의 인덱스를 0으로 초기화한다.

그리고 목표하는 숫자 n까지 모든 숫자를 만들 수 있는 조건에 도달하는 miss가 n보다 작거나 같은 동안 반복을 수행한다.
반복 수행의 조건 분기로,
배열 nums의 현재 숫자 nums[i]가 miss 보다 작거나 같으면 이 숫자를 이용해서 현재 만들 수 있는 범위를 확장한다. miss에 nums[i]를 더한 값으로 miss를 업데이트하고, 인덱스 i를 증가시켜 다음 숫자로 넘어간다.

배열에 현재 숫자 nums[i]가 miss보다 크다면 배열에 현재 miss 값을 같은 패치로 추가해 miss를 두 배로 증가시키고 패치를 추가한 횟수를 1븡가 시킨다.

miss가 주어진 n을 초과하면 반복을 종료하는데, 이 시점은 1부터 n 까지의 모든 숫자를 만들 수 있는 시점이다.

Code

def minPatches(nums, n):
    miss = 1
    added = 0
    i = 0
    while miss <= n:
        if i < len(nums) and nums[i] <= miss:
            miss += nums[i]
            i += 1
        else:
            miss += miss
            added += 1
    return added

Complexicity

시간 복잡도

while 루프는 miss가 n 보다 작거나 같을 때 반복 되고, miss는 각 반복마다 두 배로 증가해 배열의 현재 요소를 더하여 증가한다.
최악의 경우 miss가 반복적으로 두 배증가하는 경우이고 이때는 log(m)의 반복을 의미한다. 배열의 모든 요소를 탐색할 때는 o(n)이 소요되므로 최종 시간 복잡도는 O(n+log(m)) 이다.

공간 복잡도

상수 변수만 업데이트 되므로 공간복잡도는 O(1) 이다.