[LeetCode] Non-decreasing Array

문제링크

Non-decreasing Array - LeetCode

 

주어진 배열에서 하나의 숫자만 변경하여 오름차순을 만들 수 있는지 묻는 문제이다.

접근 방법

처음에는 앞 뒤 숫자만 비교하는 방식으로 접근하였지만 곧 3개의 수를 비교해야한다는 것을 깨달았다.

(2, 3, 4, 8, 3, 4, 5) => nums[i-1] > num[i] 인 구간이 1개이지만 정답일 수 없음
(1, 2, 50, 3)  => 50을 줄이거나 3을 키워야함
(1, 2, 1, 3) => 1을 키워야함
(4, 2, 3) => 4를 줄여야함..

이렇게 두 수를 비교하면 여러 경우를 모두 처리할 수 없었다. (저는 못했습니다..)

그래서 3개의 숫자를 비교하는 방식으로 진행하였다.

(편의상 nums[left], nums[mid], nums[right]를 left, mid, right로 표현)

1. left <= mid <= right 인 경우 : continue;

 if(nums[left] <= nums[mid] && nums[mid] <= nums[right]) continue;​

2. left <= mid <= right가 아닌 경우

2.1 left <= right인 경우 : left <= right < mid 이므로 mid = left 대입하고 decreasingCnt++ (예, 1, 5, 3 => 1, 1, 3)

if(nums[left] <= nums[right]){
    nums[mid] = nums[left];
    decreasingCnt++;
}​

2.2 left > right인 경우

2.2.1 left > mid > right 인 경우 : 숫자를 두개 바꿔야 오름차순이 될 수 있으므로 false (예. 4, 2, 1 => false)

if(nums[left] > nums[mid] && nums[mid] > nums[right]) return false;​

2.2.2 left > right >= mid 인 경우 : left에 mid를 대입하고 decreasingCnt++  (예, 5, 3, 4 => 3, 3, 4)

else if(nums[mid] <= nums[right]){
    nums[left] = nums[mid];
    decreasingCnt++;
}​

2.2.3 mid >= left > right인 경우 : right에 mid를 대입하고 decreasingCnt++ (예, 5, 9, 3 => 5, 9, 9)

else if(nums[mid] >= nums[left]){
    nums[right] = nums[mid];
    decreasingCnt++;
}

3. 최종적으로 바꾼 횟수가 2번 이상이면 false, 1번 이하면 true를 반환한다.

return decreasingCnt > 1 ? false : true;

 
생각보다 예외처리할 부분이 많았던 문제였다.
for문을 한번만 돌기때문에 시간 복잡도에서는 나쁘지 않았다. (O(N))

 

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
    let decreasingCnt = 0;
    
    for(let i = 0; i < nums.length - 2; i++){
        const left = i, mid = i+1, right = i+2;
        
        if(nums[left] <= nums[mid] && nums[mid] <= nums[right]) continue;
        else{
            // left <= right일때 mid를 작은 쪽으로 넣고 decrease++
            if(nums[left] <= nums[right]){
                nums[mid] = nums[left];
                decreasingCnt++;
            }
            // left > right일때
            else{
                // left > mid > right
                if(nums[left] > nums[mid] && nums[mid] > nums[right]) return false;
                // left > right >= mid일때 left = mid, decrease++
                else if(nums[mid] <= nums[right]){
                    nums[left] = nums[mid];
                    decreasingCnt++;
                }
                // mid >= left > right 일때, right = mid decrease++
                else if(nums[mid] >= nums[left]){
                    nums[right] = nums[mid];
                    decreasingCnt++;
                }
            }
        }
    }
    
    return decreasingCnt > 1 ? false : true; 
};