[LeetCode] 162. Find Peak Element - Swift

문제

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

문제 해석

Peak 요소는 이웃에 존재하는 수보다 엄격히 큰 요소이다.

정수 배열이 주어지면, Peak 요소를 찾아 인덱스를 반환합니다. 만약 여러 개의 Peak가 있는 경우 그 중 아무거나 반환하면 됩니다.

그리고 nums[-1] = nums[n] = -∞, 즉 배열 밖의 요소는 음의 무한대, 엄청나게 작은 수라 생각하면 됩니다.

문제 풀이

여기서 중요한 조건중 하나는

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

이다. 즉 이웃 되는 수와 같을 염려는 없다. 여기서 Peak이란 숫자가 산의 높이라고 생각한다면 튀어 나온 부분을 모두 Peak 이라 보면 된다. 이 중 아무거나 반환하면 끝

간단하게 생각하면 간단하게 풀리고, 어렵게 생각하면 어렵게 풀리는 문제. 

처음에는 간단하게 배열을 탐색해서 이웃의 수와 비교해서 큰 숫자를 반환하도록 풀었다. 이렇게 해도 간단하게 풀 수 있는 문제 지만, 문제의 카테고리가 binary search인 만큼 이를 이용해서 풀어 보도록 하자. 물론 내가 푼건 아니다 ㅜ

배열에서 leftPoint와 RightPoint를 잡았을 때 이 범위 안에 Peak이 존재하게끔 범위를 좁혀나가면 된다. 위의 조건처럼 이웃 되는 수는 같지 않기 때문에 무조건 감소하거나 증가하는 형태가 될 것이다.

따라서 leftPoint와 RightPoint의 중간 값과 중간 값 + 1 을 비교했을 때 이 두 수 증가하는 지, 감소하는 지 확인 한다. 만약 증가한다면, 중간 값의 오른 쪽에 Peak 요소가 존재할 것이고, 감소한다면, 왼 쪽에 Peak 요소가 존재할 것이다.

그렇다면 이 범위를 좁혀 나가기 위해서 leftPoint 또는 rightPoint를 이동한다. 위의 비교애서 증가한다면, leftPoint를 중간값+1로 옮기고, 감소한다면, rightPoint를 중간 값으로 옮긴다.

class Solution {
        func findPeakElement(_ nums: [Int]) -> Int {
        
        var leftPoint = 0
        var rightPoint = nums.count - 1
        
        while leftPoint < rightPoint {
            let mid = (leftPoint + rightPoint) / 2
            if nums[mid] < nums[mid + 1] {
                leftPoint = mid + 1
            }
            else {
                rightPoint = mid
            }
        }
        
        return leftPoint
    }
}