[leetcode] 665. Non-decreasing Array 파이썬 코드

https://leetcode.com/problems/non-decreasing-array/

 

배열이 주어졌을 때 최대 1개의 숫자를 바꿔서 오름차순 정렬되게 배열을 만들 수 있는지 묻는 문제다.

오름차순 정렬을 할 수 있으면 True를, 그렇지 않으면 False를 반환한다.

 

여기서 헷갈렸던 걸 2개의 테스트케이스를 가지고 설명할 수 있다.

nums1 = [3, 4, 2, 3]

nums2 = [-1, 4, 2, 3]

첫 번째 배열은 한 번만 바꿔서 오름차순 배열을 만들 수 없고,

두 번째 배열은 그렇게 할 수 있다.

 

i 번째 element가 i+1 번째 element보다 크면, 숫자를 바꿔줘야 한다.

그런데 2가지 경우가 있다.

(1) 첫 번째 배열처럼 i-1 번째가 i+1 보다 클 때와 (2) 두 번째 배열처럼  i-1 번째가 i+1 보다 작을 때이다.

 

(2) 번의 경우라면, i 번째 요소를 i+1 번째 값으로 바꿔준다. [-1, 2, 2, 3]

그리고 나서 warning + 1

 

(1) 번의 경우라면, i+1 번째 요소를  i 번째 값으로 바꿔준다. [3, 4, 4, 3]

그리고 나서 warning + 1

그런데 이 배열의 경우 2번째 인덱스와 3번째 인덱스에서 오름차순이 아니므로 이 배열은 False가 된다.

 

class Solution(object):
    def checkPossibility(self, nums):
        if len(nums) == 1:
            return True
        warning = 0
        lp, rp = 0, 1
        while rp < len(nums):
            if nums[lp] <= nums[rp]:
                lp += 1
                rp += 1
            else:
                warning += 1
                # decide increase / decrease the value
                if lp > 0 and nums[lp-1] > nums[rp]:
                    nums[rp] = nums[lp]
                if lp > 0 and nums[lp-1] < nums[lp]:
                    nums[lp] = nums[rp]
                lp += 1
                rp += 1
            if warning > 1:
                return False
        return True

 

 

똑같은 코드인데 조금 더 깔끔하게 써보면,

class Solution(object):
    def checkPossibility(self, nums):
        if len(nums) == 1:
            return True
        warning = 0
        lp, rp = 0, 1
        while rp < len(nums):
            if nums[lp] > nums[rp]:
                warning += 1
                # decide increase / decrease the value
                if lp > 0 and nums[lp - 1] > nums[rp]:
                    nums[rp] = nums[lp]
                if lp > 0 and nums[lp - 1] < nums[lp]:
                    nums[lp] = nums[rp]
                    
            if warning > 1:
                return False
            
            lp += 1
            rp += 1
        return True