Problem #79

벌써 79번 문제다

주어진 수열의 한 원소를 수정해 단조 증가로 만들 수 있느냐가 문제

 

non decreasing 수열의 정의를 살펴보면 쉽다

정의 :  모든 n에 대해 a(n)<=a(n+1)

만약 한개 이하의 원소만 이상해서 단조 증가성을 깨트린다면 어떨까

x번째 원소라 하면

a(x-1) < a(x) and a(x) > a(x+1)

or 

a(x-1) > a(x) and a(x) < a(x+1)

 

a(1) <= a(2) <= a(3) <= ...a(k)>a(k+1).. <= a(n-1) <= a(n)

이런 관계를 만족하는 수열에서

단 1개의 irregular가 등장해 부등호의 방향을 반대로 바꿔야 한다.

 

1. irregular의 개수를 세주기

1개 이하면 pass. 2개 이상이면 이 수열은 회복 불가

 

2. irregular가 나타나는 인덱스 k를 찾기.

 

3. 수열 복구하기

k==n-1 or a(k)<=a(k+2)이면 a(k+1)을 a(k) ~ a(k+2) 사이(경계 포함)의 임의의 수로 바꿔 주면 된다.

k==1 or a(k-1)<=a(k+1)이면 a(k)를 a(k-1)~a(k+1) 사이(경계 포함)의 임의의 수로 바꿔 주면 된다.

둘 다 아니면 이 수열은 회복 불가