[LeetCode Top Interview 150]
[문제 링크]
[문제 설명]
Peak 요소는 양 옆의 인접 요소보다 큰 요소를 뜻한다. (가장 꼭대기 요소) 0 인덱스부터 주어지는 nums 배열에서 Peak 요소를 찾고, 해당 인덱스를 반환하여라. 배열에 여러 Peak가 있는 경우 Peak 중 하나의 인덱스를 반환한다. 시간 복잡도는 O(logN)을 가진다.
Example 1
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
[처음에 내가 생각해 본 방법]
제목에서 알 수 있듯 이진 탐색 알고리즘을 활용하여 푸는 문제였다.
주어진 배열의 중간 값을 먼저 찾고, 중간 값과 찾아야 하는 값의 대소에 따라 점점 범위를 조정해나가는 식으로 생각해보았다. start 값이 커지고, end 값이 작아지면서 점점 범위가 좁혀져서 start == end의 값이 같아지는 경우, 그 때가 바로 찾는 도출 값이므로 같으면 반복문이 종료된다.
[이해를 위해 찾아본 시각자료들]
출처1 : https://yjym33.tistory.com/24
출처2 : https://roytravel.tistory.com/331
[의사 코드]
//인덱스는 0부터 시작하므로
// (가장 왼쪽의 시작값과 가장 오른쪽의 마지막값 구하기)
시작값=0, 마지막=배열 길이-1;
while(시작값<마지막값)
//중간값 구하기
중간값 = (시작값+마지막값)/2;
// 만약 현재 중간값이 오른쪽보다 작다면?
if 배열[중간] 인덱스 값 < 배열[중간 오른쪽] 인덱스 값
시작값=중간값+1;
else
마지막값=중간값;
return 시작값;[실제 구현 코드]
class Solution {
public int findPeakElement(int[] nums) {
int start=0, end=nums.length-1;
while(start<end){
int mid = (start + end) / 2;
if(nums[mid] < nums[mid+1]){
start = mid+1;
}
else{
end=mid;
}
}
return start;
}
}nums = [1,2,3,1]
1) start = 0; end = 배열의 길이-1이니까 3
2) 0<3이므로 반복문 실행
3) mid = 1;
4) nums[1] = 2, nums[2]=3;
5) 2<3이므로, start = 2; (end = 3;)
6) 2<3이므로 반복문 실해
7) mid = 2;
8) nums[2] = 3, nums[3]=1;
9) 3>1이므로, end = 2;
10) stat =2 / end = 2으로 두 값이 같으므로 반복문 종료, 찾은 값 2 return;
[고려해봐야 할 사항]
사실.. 중간 값을 구할 때 쉽게 찾으려고 간단한 식을 사용했는데,
문제를 풀고 나서 찾아보니까 만약에 (start+end) 값이 int 값의 범위(-2,147,483,648 ~ 2,147,483,647)보다 크다면, 음수 값으로 오버플로우 되어 2로 나누면 mid 값이 최종적으로 음수가 되는 문제가 생길 수도 있다고 한다.
int mid = (start + end) / 2; 그래서 만약 (start+end) 값이 int 값의 범위를 넘어가는 경우에는
아래와 같이 중간 값을 구하는 것이 좋다고 한다.
int mid = start + (end - start) / 2