[medium] 665. Non-decreasing Array

문제

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

---

풀이방법

1. 앞/뒤 방향에서 non-decreasing 조건에 맞는 숫자들인지 탐색하면서 start 인덱스와 end 인덱스를 움직인다
2. 조건에 맞지 않는 숫자가 나오면 그 위치에 인덱스를 고정한다.

• 인덱스 고정할 일 없이 while 문이 끝나면 True 리턴
• 인덱스가 고정됬는데 start 와 end의 간격이 1을 넘어가면, 이는 숫자 하나 삭제만으로는 조건을 만족시킬 수 없다는 의미이므로 False 리턴

4. 고정된 start, end 인덱스에서 nums[start] 혹은 nums[end]에 있는 숫자를 삭제해서 non-decreasing 조건에 맞출 수 있는지 체크한다

• start 인덱스를 삭제하는 경우: nums[start-1] <= nums[end] 이면 start에 있는 숫자를 제거해서 non-decreasing 조건을 만족시킬 수 있다. 따라서 True 리턴
• end 인덱스를 삭제하는 경우: nums[start] <= nums[end+1] 이면 end에 있는 숫자를 제거해서 non-decreasing 조건을 만족시킬 수 있다. 따라서 True 리턴
• 위의 경우에 해당하지 않으면 False 리턴

시간복잡도 O(N)

반응형

---

코드

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        start = 0
        end = len(nums)-1
        
        while start <= end:
            if  start < len(nums)-1 and nums[start] <= nums[start+1]:
                start += 1
            elif end > 0 and nums[end] >= nums[end-1]:
                end -= 1
            else:
                if end-start > 1:
                    return False
                else: 
                    if start == 0 or (start-1 >= 0 and nums[start-1] <= nums[end]): #start에 있는 num 삭제
                        return True
                    elif end == len(nums)-1 or (end+1 <= len(nums)-1 and nums[start] <= nums[end+1]): #end에 있는 num 삭제
                        return True
                    else:
                        return False
                
        return True