[LeetCode] 162. Find Peak Element

Find Peak Element - LeetCode

int 배열에서 좌,우 요소보다 큰 요소의 인덱스를 반환하는 문제입니다.

O(log n) 시간 내에 실행되는 알고리즘을 작성해야 합니다.

 

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.

 

문제접근

O(log n) 는 이분탐색으로 해결할 수 있기 때문에 이분탐색으로 접근하였습니다.

하지만 정렬이 되어있지 않은 배열이기에 어떻게 답을찾을까 고민을 하였습니다.

 

검색을 통해 문제 접근법을 알게되었습니다.  

 

정렬이 되어있지 않아도 요구사항을 통해 해결할 수 있습니다.

우리는 주변보다 큰 요소를 찾아야 하기때문에 pivot값을 정하고

pivot보다 다음 요소가 크다면 정답의 가능성이 있다고 판단하여

left = pivot +1

pivot보다 다음 요소가 작다면 피벗을 포함해 왼쪽에 가능성이 있기에

right = pivot 

 

이과정을 거쳐 left 또는 right를 반환하면 됩니다.

 

public int findPeakElement(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int pivot = (l + r) / 2;
            int num = nums[pivot];
            int nextNum = nums[pivot + 1];

            if (num < nextNum) {
                l = pivot + 1;
            } else {
                r = pivot;
            }
        }

        return l;
    }

 

시간복잡도

이분탐색을 사용하고 있습니다.

O(log N)안에 해결할 수 있습니다.

 

느낀점

이분탐색은 정렬된 배열에서만 사용 가능합니다.

하지만, 문제의 조건을 잘 파악하면 정렬되지 않은 배열에서도 이분탐색을 통해 정답을 도출할 수 있습니다.

 

참고

https://www.youtube.com/watch?v=zChSh4yOOCg