[Java] 162. Find Peak Element

문제 파악

주변 원소들보다 큰 원소를 peak element라고 한다.

 

그러한 원소가 여러개라면 아무 원소의 인덱스를 반환하면 된다.

 

시간 복잡도가 O(logN) 이 되도록 구현해야한다.

---

풀이

1️⃣ 이분 탐색을 이용한 풀이

💡 떠오른 Idea

시간복잡도를 통해 이분 탐색을 이용해야함을 알 수 있었다.

보통 이분탐색은 정렬된 배열에서만 사용해와서,

이분 탐색을 어떻게 활용할 수 있을지 오랫동안 생각해보았다.


mid 포인트 값이 mid + 1 포인트 값보다 작다면?

mid 포인트 값은 peak element 가 될 확률이 존재하지 않는다.

따라서 탐색 범위를 mid+1 이상으로 잡아줘야 할 것이다.


만약, mid 포인트 값이 mid + 1 포인트 값 보다 크다면

mid 포인트 값은 peak element 가 될 확률이 존재한다.

따라서, 탐색 범위를 mid 이하로 잡아줘야 한다.

 

위 아이디어를 바탕으로 코드를 구현하였다.

 

 

 

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left+right) / 2;
            if(nums[mid]<nums[mid+1]){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

 

결과

---

📖 회고

시간 복잡도를 명시해줘서, 이분탐색 방식을 떠올렸고 그에 맞게 로직을 생각하니 구현할 수 있었다.

 

로직이 직관적으로는 이해가 가는데, 수학적으로는 어떻게 증명해야할지 쉽게 떠오르지 않아서 조금 찝찝하긴하다.

 

중간 지점을 기준으로 오른쪽 원소가 더 크면 오른쪽 영역으로 이동하는데

 

오른쪽 영역에, 억지로 peak 를 만들지 않기 위해서 계속 큰 원소만 주어진다고 가정했을 때, 결국 배열의 끝 값도 peak 포인트로 인정되기 때문에 존재함을 알 수 있고

 

그렇다고 계속 큰 원소만 주어지지 않고, 작은 원소가 나타나는 순간 peak 포인트가 생기기 때문에 존재한다고 생각할 수 있겠다.