Peak 찾는 문제

Two-pointer의 단골 문제 되시겠다. GeeksforGeeks 에도 어김없이 수록.

Output인즉, 주변 값이 자신보다 작은 값을 찾으라는 것이다. (if a[i] > a[i-1] && a[i] > a[i+1] then a[i] )

Input: array[]= {5, 10, 20, 15}
Output: 20
The element 20 has neighbours 10 and 15,
both of them are less than 20.

Input: array[] = {10, 20, 15, 2, 23, 90, 67}
Output: 20 or 90
The element 20 has neighbours 10 and 15, 
both of them are less than 20, similarly 90 has neighbours 23 and 67.

그러니까, 부분 최대값 (Optimal Biggest)을 찾으란 이야기이다.

문제 자체는 간단하다. 투포인터 문제(분할정복)이 언제나 그렇듯… int l,r 을 준비해놓고, n=(l+r)/2 을 계산한 후, arr[n] 이 주변 값들보다 더 큰지(정답인지) 검사한다. 아니라면,

1. 오른쪽 값이 더 크면, 분명히 오른쪽 어딘가에 answer이 있다! 오른쪽으로 분할정복 수행.
2. 아니라면(= 왼쪽이 더 크면), 왼쪽 어딘가에 answer이 있다! 왼쪽으로 분할정복 수행.

이다.

사실 이 문제는 알고나면 별건 없지만, Sorted 되지 않은 경우에도 모든 값을 다 찾아볼 필요가 없다는 영감을 얻는 것이 핵심이다. 중간지점으로 이동해도 정답이 어디쯤 있을지 파악이 가능하기 때문에 이러한 접근이 가능하다. 왠지 Gradient Descent가 떠오르는군…

그래서 그런지 막상 부딪히면 가끔 어떻게 하더라… 맹해지는 문제 중 하나. 그래도 이런 특이한 문제 재밌다.