[LeetCode] 162. Find Peak Element

문제 출처: https://leetcode.com/problems/find-peak-element/

Find Peak Element - LeetCode

 

문제

정상(Peak) 원소는 이웃보다 엄격하게 큰 원소이다.

 

정수 배열 nums에서 정상 원소를 찾아라, 그리고 그 인덱스를 반환하라. 만약 배열에 여러 정상이 존재한다면, 정상 원소 중 어떤 인덱스를 반환해도 된다.

 

nums[-1] = nums[n] = -∞라고 생각하라.

 

O(log n) 실행 복잡도 안에 동작해야 한다.

제약조건

• nums[i] != nums[i + 1] for all valid i.

 

예제

Input: nums = [1,2,3,1]
Output: 2

Explanation: 3 is a peak element and your function should return the index number 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) 실행 시간에 대해서 생각하면, 각 단계마다 탐색 범위가 반으로 줄어드는 알고리즘에서 보이는 시간 복잡도이다. O(log n)의 시간 복잡도를 갖는 대표적인 알고리즘인 이진 탐색(Binary Search) 이다.

 

이 문제는 이진 탐색이 가능한 문제인가? 에 대해서 생각해보자.

 

일반적으로 이진 탐색은 정렬된 배열에서 특정 값이 존재하는지 찾는 알고리즘으로 알려져 있다. 이것만 생각하면 이 문제에는 적용이 불가능해 보인다.

 

이진 탐색이 동작하는 원리를 조금 더 생각해보자. 일반적인 경우에서 이진 탐색이 동작하는 것은 찾고자 하는 값이 특정 값의 오른쪽에 있는지 혹은 왼쪽에 있는지가 정렬이라는 상태에 의해서 판단 가능하기 때문이다. 즉, 중요한 것은 정렬이라는 상태보다는 찾고자 하는 값의 위치가 특정 값을 기준으로 어디에 있는지 판가름 할 수 있느냐이다.

 

위 사항을 토대로 문제를 다시 한번 살펴보자. 다음의 두가지 사항이 눈에 띈다.

1. nums[-1] = nums[n] = -∞
2. 유효한 i에 대해서 nums[i] != nums[i+1] 이다.

두번째 사항으로 인해서 배열의 임의의 점은 아래의 그림과 같이 2가지 상황만 존재하게 된다.

위 상황에서 각각 정상 지점을 찾기 위해서 탐색해야하는 범위를 생각해보면, 왼쪽의 경우 i+1 지점부터 n까지 탐색을 해야하며 값이 내려가는 부분을 찾아야하고, 오른쪽의 경우 i부터 0까지 탐색을 해야하며 값이 내려가는 지점을 찾아야한다. 만약 n 또는 0까지 탐색했을 때, 정상지점이 없다면 첫번째 사항(nums[-1] = nums[n] = -∞)에 의해서 n 또는 0 지점이 정상이 된다. 즉, 어떠한 경우라도 한쪽만 탐색하면 최소 1개의 정상 지점을 찾을 수 있다.

 

이처럼 특정 지점의 값에 따라 탐색해야 할 범위를 이분화 시킬 수 있기 때문에 이 문제는 이진 탐색 알고리즘으로 풀 수 있는 문제이다.

 

코드를 작성하면 다음과 같다.

function findPeakElement(nums) {
    let left = 0, right = nums.length-1;

    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[i] < nums[i+1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

 

Github: 162.js

opwe37/Algorithm-Study