[LeetCode] 330. Patching Array

문제 출처: https://leetcode.com/problems/patching-array/

Patching Array - LeetCode

---

문제

정렬된 정수 배열 nums 와 정수 n 이 주어지면, 배열의 일부 원소의 합이 [1, n] 범위를 모두 포함할 수 있도록 배열에 원소를 추가하라.

 

추가해야 하는 원소의 최소 숫자를 반환하라.

예제

Input: nums = [1,3], n = 6
Output: 1

Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Input: nums = [1,5,10], n = 20
Output: 2

Explanation: The two patches can be [2, 4].

Input: nums = [1,2,2], n = 5
Output: 0

---

풀이

문제의 해결의 핵심 아이디어는 다음과 같다.

 

• [0, k] 를 커버하는 배열이 존재한다고 가정해보자. 이 범위를 증가시키 위해서는 x (1 ≤ x ≤ k+1)의 값이 필요하다. 이 범위의 값을 추가하면 기존에 비해 증가된 [0, k+x]의 범위를 커버할 수 있다.

 

nums = [1, 5, 10], n = 20 인 상황을 생각해보자.

 

[0, 0]의 범위를 nums를 활용하여 최소 [0, 20]으로 만드는 것이 목표이다. 위의 아이디어를 활용하여 문제를 풀면 다음과 같다.

• [0, 0]을 증가시키기 위해 필요한 x: 1 ≤ x ≤ 1, nums에 있는가? Yes => nums[0] => [0, 1]
• [0, 1]을 증가시키기 위해 필요한 x: 1 ≤ x ≤ 2, nums에 있는가? No => 2 추가 => [0, 3]
  
  • 이전에 사용한 nums의 값은 없는 것으로 취급
  • 필요한 범위 중 가능한 가장 큰 값을 추가 => 커버 영역을 되도록 많이 증가 => 추가하는 횟수를 최소로 만들기 위함
• [0, 3]을 증가시키기 위해 필요한 x: 1 ≤ x ≤ 4, nums에 있는가? No => 4 추가 => [0, 7]
• [0, 7]을 증가시키기 위해 필요한 x: 1 ≤ x ≤ 8, nums에 있는가? Yes => nums[1] => [0, 13]
• [0, 13]을 증가시키기 위해 필요한 x: 1 ≤ x ≤ 14, nums에 있는가? Yes => nuns[2] => [0, 23]

위 방식을 코드로 작성하는데 필요한 부분에 대해 생각해보자.

 

먼저, 커버 영역을 증가시키기 위해 필요한 범위에서 실제적으로 필요한 값은 가장 큰 값이다. 즉, [0, k] 영역을 커버하고 있다면 k+1의 값을 추가하는 것이 어떤 값을 추가하는 것보다 범위를 크게 늘리기 때문이다.

 

하지만!! 현재 nums에서 사용하지 않은 값 중에서 k+1보다 작은 값이 존재한다면, 해당 값을 먼저 활용하여 범위를 늘려야 한다. 이 과정은 nums가 정렬되어 있다는 것을 활용하여 접근할 수 있다. 위 예시에서도 nums의 값을 순차적으로 활용한 것을 볼 수 있다.

 

이러한 내용을 코드로 작성하면 다음과 같다.

var minPatches = function(nums, n) {
    let answer = 0;
    
    let covered = 0;
    let i = 0;
    
    while (covered < n) {
        if (i >= nums.length || nums[i] > covered + 1) {
            answer += 1;
            covered += (covered + 1)
        } else {
            covered += nums[i];
            i += 1;
        }
    }
    
    return answer;
};

 

Github: 330.js

GitHub - opwe37/Algorithm-Study