LeetCode - Patching Array

안녕하세요. 그린입니다🟢

이번 포스팅에서는 오랜만에 알고리즘을 하나 풀어볼까합니다.

이번에는 LeetCode에서 Patching Array라는 문제를 풀어봤어요!

 

문제제시

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] <= 104
• nums is sorted in ascending order.
• 1 <= n <= 231 - 1

문제풀이

class Solution {
  func minPatches(_ nums: [Int], _ n: Int) -> Int {
    var sum = 0
    var indexOfNums = 0
    var emptyNumsCount = 0
        
    while sum < n {
      if indexOfNums < nums.count 
      && nums[indexOfNums] <= sum + 1 {
        sum += nums[indexOfNums]
        indexOfNums += 1        
      } else {
        sum += sum + 1
        emptyNumsCount += 1   
      }
    }
    return emptyNumsCount
  }
}

먼저 문제를 해석해봐야겠죠?

배열이 주어질때 해당 배열의 요소를 한번씩 쓸수 있습니다.

해당 요소들을 조합해서 주어진 n까지 즉 1부터 n까지의 양의 정수중 만들 수 없는 숫자가 있습니다.

이 숫자를 만들기 위해서 필요한 양의 정수값의 갯수를 구하는 문제입니다..!

음 난이도가 조금 있다고 생각해요🧐

그렇지만 모든 알고리즘이 그렇듯 조금 깊게 생각해보면 간단히 풀 수 있는 방법이 존재하죠!

저는 이렇게 접근해봤습니다🙋🏻

우선 세가지 변수를 위와 같이 만듭니다.

그리고 조건을 만족할때까지 while문을 돕니다.

어떤 조건이냐..!

우선 배열의 들어있는 요소의 갯수보다 indexOfNums가 크지 않아야하고

총합인 sum+1보다 요소의 크기가 작거나 같을때입니다.

이럴때는 총합에 해당 요소들을 올려주며 다음 요소의 인덱스로 접근해줍니다.

만약 위 조건에 부합하지 않으면 sum에 1을 더해준 값을 중복으로 더해줍니다.

그리고 emptyNumsCount가 비어있는 요소가 될것임으로 갯수 카운트를 증가시켜줍니다.

마지막으로 해당 값을 반환하면 아래와 같은 100% 만족된 결과를 얻을 수 있습니다!

 

풀이결과

 

마무리

아.. LeetCode는 처음이라 조금 해맸는데 그래도 기존에 하던 Codility와 굉장히 비슷하다고 느껴져 툴의 사용에서는 괜찮았습니다.

그냥 Codility를 쭉할까 했는데 어느순간 질려서 안하고 있더라구요.

그래서 이번에 다른 환경에서 해봤습니다!!

 

[참고자료]

https://leetcode.com/problems/patching-array/submissions/

Patching Array - LeetCode