[LeetCode] 162. Find Peak Element [Python] 이진탐색

 

leetcode.com/problems/find-peak-element/

Find Peak Element - LeetCode

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

Given an input array nums, where nums[i] ≠ nums [i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

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

 

해당 문제는 꼭대기를 찾아 그 꼭대기가 존재하는 인덱스의 값을 리턴하는 것이다. 이 문제에서 놓치지 말아야 할 포인트는 You may imagine that nums[-1] = nums [n] = -∞. 이 부분인것 같다. 즉, [1, 2, 3, 4]의 어레이가 주어졌을 때, 어레이만 보았을 때는 peak는 없지만, index -1과 index 0에 - inf 값이 있다고 보는 것이다. 그러므로 주어진 array에서 꼭대기는 늘 존재한다. 또한 global peak를 찾을 필요 없이, local peak을 찾아도 된다 -- The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. 이 문제를 푸는 방법은 여러가지가 있겠지만, 먼저 1줄 코딩이 가능한 것은 아무래도 max와 index 함수를 쓰는 것.

 

---

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        return nums.index(max(nums))

---

max function을 이용하여 nums에서 가장 큰 값을 찾은 후, 그 값의 index를 index function을 이용하여 찾아내 리턴하는 것이다. 이경우 local peak가 아닌 global peak를 리턴하게 된다.

---

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
    	m, idx = -1, -1
        # m -- the current max value
        # i -- the index of m
        
        for i, v in enumerate(nums):
            if v > m: 
            	m = v
                idx = i
        return i

---

위의 솔루션은 max()와 index()를 사용하지 않고 풀어쓴 것이다. 이 경우, space complexity O(1) time complexity O(n)이 나오게 된다. 이와 비슷한 방법으로, local peak를 찾아 리턴하는 방법도 작성해볼 수 있다. nums [i-1] < nums [i] > nums [i+1]인 경우를 찾게 되자마자 바로 i를 return 하는 것이다. 위의 솔루션의 경우엔 best, avg, worst 모든 케이스가 O(n)이지만, 이 경우엔 best case의 runtime이 global peak을 찾는 알고리즘보다 더 낫다. 그러나 역시, worst case는 똑같이 O(n)이 나온다. 그렇다면 더 빠르게 할 수 있는 방법은 없을까?

 

 

---

class Solution:
    def findPeakElement(self, nums):
        left, right = 0, len(nums)-1

        while left < right:
            mid = left + (right-left)//2
            if nums[mid] < nums[mid+1]: 
                left = mid+1
            else: 
                right = mid

        return left

---

위의 솔루션은 binary search를 이용하여 푼 것이다. left를 local peak을 찾는 기준점으로 보고, mid index에 있는 값을 그 앞에 있는 element와 비교하여 큰 값이 있는 index를 left값이 가지게끔 한다. 이 문제는 local peak를 찾는 것이므로, element 값이 증가하지 않는 그 시점만 찾으면 된다. 때문에 이진 탐색을 이용했을 때, 언제나 peak를 찾을 수 있다. 이 솔루션의 경우 space O(1) runtime O(logn)이 나온다. 앞의 솔루션보다 더 나은 runtime performance를 보여준다.