[c++/LeetCode-Array] 162. Find Peak Element

 

난이도: Medium

키워드: Array

 

문제

문제 원문:  https://leetcode.com/problems/find-peak-element/description/

 

 

Peak 요소는 이웃보다 엄격하게 큰 요소를 뜻한다. 0부터 색인이 지정된 정수 배열 nums가 주어졌을 때, Peak 요소를 찾고 해당 색인을 반환하라. 배열에 여러 개의 Peak이 포함되어 있으면 어떤 Peak의 색인이든 반환할 수 있다.

nums[-1] = nums[n] = -∞로 간주해도 된다. 즉, 배열 외부에 있는 이웃보다 요소는 항상 엄격하게 크다고 간주된다.
O(log n) 시간 내에 실행되는 알고리즘을 작성해야 한다.

 

문제 풀이

 

문제 자체만 놓고 보면 Medium 난이도는 아니다. 가장 쉽게 생각해보면 O(n) 안에 iteration을 돌면서 pivot 조건을 만족하는 값을 찾아서 반환해주면 된다. 하지만 문제에서 복잡도를 O(log n) 이내로  수행하도록 제한했다.

 

O(log n) 복잡도로부터 쉽게 떠올릴 수 있는 방법이 binary search이다. 그래서 bin_search를 적용해서 문제를 풀어봤다.

pivot은 결국 local / global maxima기 때문에 현재 값을 기준으로 더 큰 값이 있을 것 같은 곳을 찾아서 따라가면 된다. 더욱이, 마지막 값은 boundary의 값이 -∞로 간주된다고 해주었기 때문에 문제를 복잡하게 생각할 것 없다.

 

mid값을 기준으로 mid보다 큰 값이 있는 방향으로 search space를 좁히다가 left = right가 되었을 때 가리키는 값을 반환해주면 된다. 오랜만에 cpp로 작성해봤다.

 

#include <vector>

using namespace std;

class Solution {
public:
    int findPeakElement(vector<int>& nums) {

        int left = 0;
        int right = nums.size() - 1;

        if(nums.size() <= 1){
            return 0;
        }

        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < nums[mid+1]){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
};