<Hard> Patching Array (LeetCode : C#)

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

📕 문제 설명

정렬된 정수 배열 nums와 정수 n이 주어질 때 [1, n] 범위를 만들 수 있게 숫자를 붙인다. 붙일 숫자의 최소 개수 반환하기

숫자를 만들때는 주어진 숫자들을 조합한 합들로 만든다. -> 예제 참고

• Input
  정수 배열 nums, 정수 n
• Output
  [1, n] 범위 만들 수 있게 하는 최소의 붙여야할 element 수

예제

예를 들어 [1,3]이 주어진 배열이고 1~6까지 만들어야 하는 경우를 보자. 2를 추가하게 되면 1, 2, 3, [1, 3], [2, 3], [1, 2, 3] 으로 1~6까지 만들 수 있으므로 2 하나만 추가하면 된다. 따라서 output이 1이된다.

풀이

nums 돌면서 값들 더해나가고 없는 경우는 count 증가시키는 식으로 해서 n 만들 수 있을때까지 반복하는식

public class Solution {
    public int MinPatches(int[] nums, int n) {
        int i = 0, result = 0, len = nums.Length;
        long max = 0;
        
        while (max < n) // n보다 작을때
        {
            if (i < len && nums[i] <= (max + 1)) // index가 nums 길이 안넘을때 + 총합보다 nums[i]가 작을때
            {
                max += nums[i]; // 총합에 요소 추가 
                i++; // 다음 숫자 보기 
            }
            else 
            {
                max += (max + 1); // 현재 없는 숫자 추가해주기 
                result++; // 개수 증가해주기 
            }
        }
        
        return result;
    }
}

결과