LeetCode - 1827. Minimum Operations to Make the Array Increasing

Solution

var minOperations = function(nums) {
    let count = 0

    for(let i=1; i<nums.length; i++) {
        if(nums[i] > nums[i-1]) {
            continue
        } else {
            const change = nums[i-1] - nums[i] + 1
            count += change
            nums[i] += change
        }
    }

    return count;
};

Explanation

이 문제의 요지는 수열을 오름차순으로 만들기 위한 최소한의 연산 횟수를 구하는 것이다.
여기서 말하는 1회 연산이란 수열의 한 수를 정하고 그 수를 1증가시키는 것이다.

그러면 수열이 오름차순이 되기 위해서는 더도 말고 덜도 말고 어떤 요소의 다음 요소가 1!!!만큼만 커도된다.
이것은 탐욕알고리즘을 통해 구할 수 있다.

• i요소가 i-1요소보다 클 경우
  : 연산할 필요가 없다.
• i요소가 i-1요소보다 작거나 같을 경우
  : 두 요소의 차 + 1 값을 i요소에 더해주면 된다. 여기서 1회 연산은 1만큼만 증가시키는 것이기 때문에 연산 횟수는 두 요소의 차 + 1가 된다.
  그리고 주의할 점이 기존 i요소를 연산 결과값으로 바꿔줘야한다. 그래야 다음 요소도 오름차순으로 만들 수 있다.

위 과정을 0번째가 아닌 1번째 요소부터 반복하면 된다.