https://leetcode.com/problems/find-peak-element
평가
결과 : 실패 후 성공
풀이시간 : 1시간 + 30분
logN이라면 명확하다. 이진탐색밖에 없다.
그러나 이진탐색은 정렬된 데이터에 대해서만 가능하다.
정렬되지 않은 데이터에 어떻게 이진탐색을 적용할 수 있을까 고민을 했다.
고민 끝에 정답을 찾았다. 문제 해결!!
아이디어
문제에서 요구하는 건 Peek Point를 찾는 겁니다.
Peek Point란 무엇이냐. 내가 인접한 왼쪽, 오른쪽 값보다 큰 값을 갖는 Point입니다.
그림으로 나타내면 이런 모양을 갖습니다.
위 그림에서 8은 왼쪽의 6, 오른쪽의 7보다 크기 때문에 Peek Point가 됩니다.
즉, 다음 조건을 만족하는 Point를 찾아야 합니다.
1. 왼쪽보다 큰 값
2. 오른쪽보다 큰 값다시 말해 Peek Point라는 말은 ^ 라는 모양의 꼭지점이 되겠죠?
이 문제를 풀기 위해 되게 중요한 말입니다. 일단 ^ 라는 모양을 기억하고 넘어갑시다.
그런데.. 문제는 원소들이 정렬되어 있지 않다는 겁니다.
정렬되어 있지 않은데 어떻게 탐색 이라는 걸 할 수 있을까요?
탐색 을 하기 위해서는 내가 현재 값에서 어느 방향으로 이동해야 정답을 찾을 수 있을지 추측할 수 있어야 합니다.
이 문제에서는 다음과 같은 방식을 통해 탐색을 진행하는데요. 그림을 통해 설명드리겠습니다.
먼저 문제를 그래프로 옮겨 보았습니다.
문제에는 nums[-1] = nums[n] = -∞ 라는 조건이 있습니다.
해당 조건을 그림으로 표현해보면 위와 같이 나오는 걸 확인할 수 있습니다.
위 그래프에서 아무 점이나 하나 찍어보겠습니다!
먼저 위 점이 Peek Point인지 확인하기 위해 양쪽 옆을 확인합니다.
운이 좋았습니다. 처음에 확인한 이 숫자가 바로 Peek Point가 됩니다.
이런 상황에서는 더 볼 필요가 없죠.
또 가능한 경우는 어떤 경우가 있을까요?
아쉽게도 8은 Peek Point가 아닙니다.
하지만 위 숫자가 Peek Point가 아니더라도 실망할 필요는 없습니다.
정답을 찾을 수 있는 근거가 생겼거든요.
그림을 다시 한 번 보여드리겠습니다.
9가 추가되면서 꺾이는 지점이 생겼습니다. -∞ 와 9를 잇는 선과 9와 8을 잇는 선이 엇갈렸습니다.
즉, 8 | 9 | -∞ 사이에서는 무조건 꺾이는 지점이 있어야 합니다.
최소한 한 지점에서는 ^ 모양이 만들어지게 돼요.
그 말은 왼쪽으로 이동하면 Peek Point를 찾을 수 있다는 이야기겠죠?
마지막으로 가능한 상황은 이런 상황이 있겠죠?
이런 상황에서는 오른쪽으로 이동하면서 Peek Point를 찾으면 됩니다~~
다른 조건들은 나올 수 없어요. 왜냐! nums[i] != nums[i + 1] 라는 조건이 있기 때문이죠.
위 세 가지 상황을 제외하고는 나올 수 없습니다.
즉, 지금 점을 기준으로 양 쪽을 검사하면 어디로 이동할지 결정할 수 있다는 말이죠~~
설명은 여기서 마무리짓고 코드를 살펴보겠습니다.
정답 코드
class Solution {
public int findPeakElement(int[] nums) {
int start = 0;
int end = nums.length;
while(start < end) {
int mid = (start + end)/2;
// 왼쪽으로 갈 수 있는 상황
// - 내기준 왼쪽 애가 값이 더 큼
boolean goLeft = (mid != 0 && nums[mid - 1] > nums[mid]);
// 오른쪽으로 갈 수 있는 상황
// - 내기준 오른쪽 애가 값이 더 큼
boolean goRight = (mid !=nums.length - 1 && nums[mid] < nums[mid+1]);
// 양쪽 다 갈 수 없으면 -> 꼭짓점이라는 의미
if (!goLeft && !goRight) {
return mid;
}
if (goLeft) {
end = mid;
} else {
start = mid + 1;
}
}
// 불가능한 상황
return -1;
}
}