[Binary Search][Medium] 162. Find Peak Element

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

Find Peak Element - LeetCode

 

Q. nums 배열이 주어질 때, 특정 원소가 인접한 두개의 원소보다 크면 peak하다 라고 한다. 이때 peak한 원소의 index를 찾아 반환하라.

 이때, 배열의 시작과 끝은 배열 밖 원소보다 항상 크다고 가정한다.

 n위치의 원소의 값은 n+1위치와 항상 다르다. 

 TC를 O(logN)이 되도록 알고리즘을 작성하라. 

 

Solution. 

 재미있는 문제다. 

 O(logN)으로 풀어야 하므로, binary search가 자동으로 머리에 떠올려진다.

 일단 그 전에 O(N)의 일반적인 방법으로 풀어보자. 

 

int findPeakElement(vector<int>& nums)
{
    if (nums.size() == 0)	return -1;

    long prev = ((long)nums[0]) - 1;
    for (int q = 0; q < nums.size(); ++q)
    {
        long next = q < nums.size() - 1 ? nums[q + 1] : ((long)nums[q]) - 1;
        if (nums[q] > prev && nums[q] > next)
            return q;
        prev = nums[q];
    }
    return -1;
}

 

그럭저럭 나쁘지 않다. 

 

하지만, 출제 의도대로 binary seach를 사용해 보자. 

 

우선 binary seach의 단 하나의 제한은, 

반을 취하고 나머지 반을 버리는 탐색 특성상, 해를 찾기위해 input이 정렬 되어 있어야 한다는 것이다. 

하지만, 이 문제는 그렇지 않다. 

즉, 반을 버리는 과정에서 잘못된 부분을 취하면 결과적으로 해를 찾지 못할 가능성이 있다. 그래서 과연 binary search에 적합한 문제인가, 먼저 검토가 필요하다. 

 

출제 조건에서 여러 해 중 어떤 해의 index만 찾아도 된다고 하였다. 따라서 아예 못찾는 경우만 제외하고 어떤 경우든, 찾기만 하면 될 것 같다. 

못찾는 경우는 두가지다. 

 끝까지 갔는데 그런 값이 없는 경우, 

 값들이 같아서 peak가 안되는 경우인데, 

 출제 조건에서 끝값들은 늘, 배열 바깥 값보다 크다 하였으며, 

 nums[i] != nums[i+1] 이라 하였다. 

 따라서 binary search에 의해 오답이 찾아질 가능성이 문제 제한조건에 의해 모두 소거 되었다.!

 

따라서 이진 탐색을 풀이에 적용해 본다. 

 

int peak_helper(vector<int>& nums, int left, int right)
{
    if (left > right)	// No Peak Found ?
        return -1;

    int mid = left + (right - left) / 2;

    long prev = mid - 1 < 0 ? ((long)nums[mid]) - 1 : nums[mid - 1];
    long next = mid + 1 >= nums.size() ? ((long)nums[mid] - 1) : nums[mid + 1];

    if (nums[mid] > prev && nums[mid] > next)
        return mid;

    if (nums[mid] < prev)
        return peak_helper(nums, left, mid - 1);

    return peak_helper(nums, mid + 1, right);
}

int findPeakElement(vector<int>& nums)
{
    return peak_helper(nums, 0, nums.size() - 1);
}

 

문제가 잘 해결 되었음을 알수 있다.