ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • LeetCode - Patching Array
    Algorithm 2021. 12. 10. 20:32

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

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

    이번에는 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

    Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

    leetcode.com

     

    'Algorithm' 카테고리의 다른 글

    LeetCode - Palindrome Number  (0) 2022.01.07
    LeetCode - Suffle an Array  (0) 2021.12.13
    Codility - Distinct  (0) 2021.10.17
    Codility - CountDiv  (0) 2021.09.12
    합을 이용한 알고리즘  (0) 2021.08.29
Designed by Tistory.