[Python-Study Leetcode 문제풀이] 665. Non-decreasing Array

Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element. We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2). Example 1: Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array. Example 2: Input: nums = [4,2,1] Output: false Explanation: You can't get a non-decreasing array by modify at most one element. Constraints: 1 <= n <= 10 ^ 4 - 10 ^ 5 <= nums[i] <= 10 ^ 5

 

해당 문제는 배열안의 숫자를 하나만 바꾸거나, 바꾸지 않았을 때 모두 증가하는 추세의 배열인지를 확인하는 문제이다.

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

> 해당 배열의 경우, 4를 2 이하의 값으로 변경 시 Pass

 

 

Input: nums = [4,2,1]
Output: false
Explanation: You can't get a non-decreasing array by modify at most one element.

> [4, 2, 1]의 경우, 2개 이상의 수를 변경해야 하므로, Fail

 

 

[Solution Code]

[1, 2, 3, 4, 5, 6, 4] 라는 배열이 있다고 가정하자

그러면, 각 숫자의 차이값을 계산한다면

[1, 2, 3, 4, 5, 6, 5]

          ↓

  [1, 1, 1, 1, 1, -1] 이라는 배열을 얻을 수 있다.

 

 

1) 이때, 모든 배열의 값이 0보다 크거나 같다면, 해당 배열은 모두 증가하는 추세이므로 True를 반환시킨다.

2) 배열이 -값을 가지게 될 경우

    2-1) 1개의 음수 값을 가질 경우, 이 경우에는 배열의 시작과 끝의 값이 -일 값일 경우 Pass 시켜야 한다

           ▶ [-1, -3, 5, 7] 의 경우, 첫 번째 -1 -> -3으로 갈 때에만 -2 감소하게 되고  -3의 값만 -1~5 사이의 값으면 변경

           ▶ 끝의 값이 음수일 경우에도 마찬가지

    2-3) 배열의 시작과 끝이 음수값이 아닐 경우

           아래의 배열을 보자

           . 해당 배열의 경우 idx = 2 에서 감소하게 되는데, 중요한 것은 다음번 idx =3의 증가값이 이전 값의 절대값과 같거나 크면, Pass가 된다

배열값	1	3	5	3	5	7
idx	0	1	2	3	4	5
+/- 값	+2	+2	-2	+2	+2	-

         

           . 하기의 배열의 경우에도, idx=1 에서 -2 감소하는데 이 경우 idx=2에서의 값이 idx=1의 증가값(+1)이 abs(-2) 보다 작다. 하지만, 그 이전의 값(idx=0 의 증가값)이 abs(-2)보다 크거나 같다면 해당 배열의 경우에도 Pass가 된다.

	-1	4	2	3	4
idx	0	1	2	3	4
+/- 값	+5	-2	+1	+1	-

     

     2-3) 2개의 이상의 음수값을 가질 경우, Fail

 

class Solution:
    def checkPossibility(self, nums: list) -> bool:
        
 
        if len(nums)<=2:
            return True
        
 
        cnt=0
        list_find = []
        for _ in range(len(nums)-1):
            list_find.append(nums[_+1]-nums[_])
 
            if nums[_+1]-nums[_] < 0:
                idx = _
                cnt+=1
                if cnt>=2:
                    return False
    
        if cnt==0:
            return True
        elif cnt<=1 and list_find[0] <0:
            return True
        elif cnt<=1 and idx == (len(nums)-2):
            return True #배열의 시작과 끝이 음수값이 아닐 경우 (Case 2-3)
        elif cnt<=1 and abs(nums[idx+1]-nums[idx]) <= (nums[idx+2]-nums[idx+1]) or abs(nums[idx+1]-nums[idx]) <= (nums[idx]-nums[idx-1]):
            return True
        else:
            return False

 

 

 

평균 아래 속도... Study 시급하다..