[LeetCode | Python] 162. Find Peak Element

느낀점

시간 복잡도에서 O(log N)이면 이진 탐색부터 생각하자.

 

문제

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

 

1차원 배열에서 피크 지점을 찾는 문제이며 시간 제약이 있다.

풀이

이진탐색을 약간 변형한다. 선택한 배열에서 양쪽의 높이를 확인하며 탐색 범위를 변경해 나아간다.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            mid = (l+r)//2
            if nums[mid] > nums[mid+1]:
                r = mid
            else:
                l = mid + 1
        return l

 

결과

• 공간복잡도: $$ O(log n) $$
• 시간복잡도: $$ O(1) $$