[leetcode #330] Patching Array
Problem
Given a sorted integer array nums and an integer n, add/patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
Example 1:
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.
Example 2:
Input: nums = [1,5,10], n = 20 Output: 2 Explanation: The two patches can be [2, 4].
Example 3:
Input: nums = [1,2,2], n = 5 Output: 0
Constraints:
・ 1 <= nums.length <= 1000 ・ 1 <= nums[i] <= 10⁴ ・ nums is sorted in ascending order. ・ 1 <= n <= 2³¹ - 1
Idea
이번 문제도 풀지 못 했다. 처음엔 주어진 값을 running sum을 이용해 계산한 후 set에 넣고 빈 값을 채우려고 했는데, 빈 값을 찾는게 어려워 배보다 배꼽이 더 큰 격이 되어버렸다. 답을 찾아보니 의외로 간단했다.
nums로 주어진 값을 순차적으로 탐색하면서 없는 값을 계산하는데, 없는 값이 탐색하고 있는 nums의 값보다 작거나 같을 경우 patch하는 값이 된다. [1,5,10]을 예로 들어보자. 없는 값을 miss로 하고 처음에 1로 설정을 한다.
miss = 1, nums[0] = 1 → nums[0] ≦ 1
next miss → nums[0] + miss = 2
nums[0] → nums[1]
이럴 경우 1이 이미 있으므로 patch할 필요가 없다. 다음 탐색할 대상은 miss + nums[0]인 2가 된다.
miss = 2, nums[1] = 5 → nums[1] > 2
patch → 2
next miss → miss + miss = 4
nums[1]이 2보다 크므로 2를 만들 방법이 없다. 따라서 2는 반드시 patch해야 할 대상이 된다. patch한 수로 miss인 값을 만들었으면 다음으로 채워야 할 값은 miss의 2배가 된다. 왜냐하면 miss보다 작은 수는 이미 다른 수들의 조합으로 만들 수 있기 때문에 miss * 2보다 작은 수도 전부 만들 수 있다.
miss = 4, nums[1] = 5 → nums[1] > 4
patch → 4
next miss → miss + miss = 8
4도 없으므로 4도 patch를 하고 8을 만들 수 있는지 확인한다.
miss = 8, nums[1] = 5 → nums[1] ≦ 8
next miss → miss + 5 = 13
nums[1] → nums[2]
1~7까지를 만들 수 있는데 nums[1]이 5이므로 1~12까지의 수도 만들 수 있다.
miss = 13, nums[2] = 10 → nums[2] ≦ 13
next miss → miss + 10 = 23
1~12까지의 수를 만들 수 있는데 nums[2]가 10이므로 1~22까지의 수도 만들 수 있다.
n이 20이므로 2와 4만 patch하면 1~20까지의 수를 조합해서 만들 수 있다.
알고리즘은 다음과 같다.
- 채워야 할 수 (miss)를 1으로 설정한 뒤 nums를 탐색한다.
- miss가 n보다 작거나 같을 때까지 탐색한다.
a. 현재 탐색하는 array의 값이 miss보다 작거나 같을 경우 miss에 해당 값을 더하고 다음 값으로 넘어간다.
b. 현재 탐색하는 array의 값이 miss보다 클 경우 miss에 miss를 더하고 patch count를 증가시킨다.- 탐색이 끝난 뒤 patch count를 리턴한다.
문제를 풀고 나니 너무 재미있었던 문제라는 생각이 들었다. 이런 방식으로 문제를 풀 수 있다니!
Solution
class Solution { public int minPatches(int[] nums, int n) { long miss = 1; int count = 0; int i = 0; while(miss <= n){ if(i<nums.length && nums[i] <= miss){ miss = miss + nums[i]; i++; }else{ miss += miss; count++; } } return count; } }
Reference
https://leetcode.com/problems/patching-array/
Author And Source
이 문제에 관하여([leetcode #330] Patching Array), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@timevoyage/leetcode-330-Patching-Array저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)