[Leetcode][665] Non-decreasing Array

문제 : leetcode.com/problems/non-decreasing-array/

---

정수형 배열이 주어질 때 최대 한 개의 요소를 수정하여 감소하지 않는 배열을 만들 수 있는지를 구하라.

---

만들고자 하는 배열은 증가하는 배열이 아닌, 감소하지 않는 배열이므로 증가하는 수를 찾아 바로 앞이나 뒤에 있는 요소와 같은 수로 변경시킨다. (기본 아이디어)

 

앞에서부터 배열을 탐색하면서 탐색 중인 인덱스가 i일 때, nums[i] > nums[i+1] (감소하는 구간)인 경우 i를 변수를 만들어 저장해둔다. (let, ind). 만일 ind 변수가 2번 이상 세팅되려고 할 땐 두 개의 요소를 수정해야 하므로 감소하지 않는 배열을 만들 수 없다.

 

모든 배열을 탐색했을 때, ind 변수가 세팅된적이 없거나 (모든 요소가 이미 감소하지 않은 배열인 경우), ind가 0이나 n-1인 경우는 nums[ind]를 nums[1]이나 nums[n-2]로 변경하면 조건을 만족하므로 true를 반환한다.

 

만약 ind변수가 1이상 n-2 이하인 경우 두가지를 체크해봐야한다.

i) 4 4 2 5 -> 4 4 4 5

ii) 1 4 2 5 -> 1 1 2 5

위 두 경우를 살펴보자.

두 가지 경우 모두 ind는 1이 된다. 하지만 정답 배열을 만들기 위해 변경해야 하는 인덱스는 i)는 2, ii)는 1 이다.

즉, i)는 ind의 다음 인덱스가 변경되는 경우인 nums[ind] <= nums[ind+2] 를 판단해야 하고, ii)는 ind가 변경되는 경우인 nums[ind-1] <= nums[ind+1] 을 충족하는지 확인해야 한다.

두 경우를 판단했을 때 둘 중 하나라도 true라면 true가 정답이 된다.

 

시간복잡도는 O(N).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/665.%20Non-decreasing%20Array.cpp