참고
문제해설
NOTE
•
입력 값 ⇒ 정수 배열
•
출력 값 ⇒ 인접 요소보다 큰 피크의 idx를 반환한다!
•
O(log n)의 시간복잡도를 가져야 한다!
문제 로직고민
NOTE
•
O(log n)의 시간복잡도를 가진다는걸 핵심으로 생각한다.
◦
일반적으로 바이너리 서치에서 나오는 시간복잡도인데, 이는 진행단계마다 절반씩 크기가 줄어들게 연산을 수행한다는 의미이다.
◦
그렇다면 절반씩 쪼개면서 진행하는 방식으로 피크를 찾을수 있는 알고리즘이 있다는건데 그게 무엇일까?
◦
1시간정도 고민했는데 도저히 생각이 안나서 토론에 들어가서 힌트를 얻었다. 그런데 방법은 알겠는데 그 방법이 왜 통하는건지는 잘 이해가 안된다.
◦
왜 이해가 안되는지 반레를 세우다가 제약사항을 확인했다.
▪
중앙값이 5, 중앙값 +1이 7일때 중앙값 ~ 끝의 범위가 모두 7이면 성립되지 않는다 생각
▪
nums[i] != nums[i + 1]
▪
이 제약조건으로 인해 내가 초기에 생각한 반례가 생략되고 위의 공식이 성립된다.
작성코드
NOTE
class Solution {
public int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length -1;
int pivot = 0;
while(left < right){
pivot = (left + right) / 2;
if(nums[pivot] < nums[pivot + 1]) left = pivot + 1;
else right = pivot;
}
return left;
}
}
Java
복사
정답코드
NOTE
class Solution {
public int findPeakElement(int[] arr) {
int start=0,end = arr.length-1;
int mid = (start+end)/2;
while(start<end){
mid = (start+end)/2;
if(mid<arr.length-1 && arr[mid] > arr[mid+1]){
end = mid;
}
else{
start = mid+1;
}
}
return end;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
뭐가 다른건지 잘모르겠다 메모리가 실질적으로 2MB차이가 나므로 그렇게 큰 차이가 아니라고 생각하고 넘어가겠다.