LeetCode 162번: Find Peak Element(JAVA)
❔ 문제
Int형 배열 nums에서 어떤 한 값이 바로 이웃한 값들보다 큰 peak element의 index를 출력하는 문제.
⏩ 예시
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: 3 is a peak element and your function should return the index number 2.
❕ 문제풀이
public int findPeakElement(int[] arr) {
if(arr.length == 1) return 0; // 1.
for(int i=0; i<arr.length; i++){
if(i==0){ // 2.
if(arr[i] > arr[i+1]) return 0;
continue;
}
if(i==arr.length-1){ // 3.
if(arr[i-1] < arr[i]) return arr.length-1;
continue;
}
if(arr[i-1] < arr[i] && arr[i] > arr[i+1]) return i; // 4.
}
return 0;
}
- 배열의 길이가 1이라면 인덱스 그대로를 반환한다.
- i=0 (배열의 처음) 이라면 i=1 보다만 크면 조건을 성립한다.
- i=arr.length-1 (배열의 끝) 이라면 i=arr.length-2 보다만 크면 조건을 성립한다.
- 그 외의 경우에는 arr[i-1] < arr[i] > arr[i+1] 을 만족하면 조건을 성립한다.
💯 고찰
멘토님이 찝어주신 문제 유형은 Binary Search 였지만 어떻게 생각해봐도 이진탐색 유형으로 생각이 나지 않았다.
결국 무식하게 for문을 돌림으로써 브루트포스 방식이 되고 말았다.
public int findPeakElement(int[] arr) {
int x = 0;
int y = arr.length -1;
while(x < y){
int mid = x + (y - x) / 2;
if(arr[mid] > arr[mid + 1]){
y = mid;
}
else{
x = mid + 1;
}
}
return x;
}
참고한 위 솔루션은 Binary Search 를 이용한 풀이였다.
코드를 처음보고 전형적인 Binary Search 기본 코드인데, 이것이 peak element를 찾는데 적합한가에 대한 의문이 들었다.
계속 고심하던 끝에 프로세스를 상상해보니 충분히 적합한 코드라는 것을 알 수 있었다.
‘최대값을 찾는다’와는 엄연히 다르다.
[1200, 1, 2, 3, 4, 5, 6, 7] 과 같은 배열에서 1200이 최대값이며 peak element가 될 수 있지만 위 코드로는 설명이 되지 않기 때문이다.
어떤 한 값을 선택했을 때, 우측의 값과 비교하여 큰 쪽으로 범위를 줄여나간다고 하자.
- 중간 값이 왼쪽 경계와 만난다.
- 중간 값이 경계와 만나지 않는다.
- 중간 값이 오른쪽 경계와 만난다.
2번의 경우 계속 시행하면 1,3번의 경우를 만날 것이고 1,3번의 경우는 시행의 결과로 인해 경계와 닿아있는 값보다는 큰 값이 된다. 결국 범위가 좁고 좁아져 하나의 peak element에 도달하게 된다.
