[LeetCode 75] Medium - 162. Find Peak Element

 

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]:  # 오른쪽으로 이동
                l = mid + 1
            else:  # 왼쪽으로 이동
                r = mid

        return l

162. Find Peak Element

 

https://youtu.be/kMzJy9es7Hc?si=qJwIqyACFE9BAEzX

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l,r = 0, len(nums)-1

        while l<=r:
            m = (l+r)//2

            if 0 < m and nums[m] < nums[m-1]: # 왼쪽이 더 크면, 왼쪽으로 가야됨
                r = m-1
            elif m<len(nums)-1 and nums[m] < nums[m+1]: # <-- 에러 발생 X
                """
                elif nums[m] < nums[m+1] and m<len(nums)-1: <-- 에러 발생 O

                Python에서는 논리 표현식에서 앞부분의 조건이 False이면 
                뒷부분은 평가하지 않음이라는 특징이 있습니다.

                nums[m] < nums[m+1]이 먼저 평가됩니다.
                만약 m == len(nums) - 1인 경우, 
                nums[m+1]에 접근하면 IndexError가 발생합니다.
                이는 Python이 논리식의 앞부분부터 차례로 평가하기 때문에 발생합니다.
                """

                # 오른쪽이 더 크면, 오른쪽으로 가야 됨
                l = m+1
            else: # 아니면 피크값임
                return m

 

시간 복잡도가 O (log n) 이므로, 이진 탐색으로 풀어야 함 !

 

풀이1)

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # 알고리즘 시간 복잡도: O (log n) => 이진 탐색
        
        l, r = 0, len(nums)-1

        while l<=r:
            mid = (l+r) //2

            # 배열 범위 안벗어나게..
            if mid+1 <= len(nums)-1 and nums[mid] < nums[mid+1]: 
                l = mid + 1
            elif 0<=mid-1 and nums[mid-1] > nums[mid]: 
                r = mid -1
            else:
                return mid

 

풀이2)

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]:  # 오른쪽으로 이동
                l = mid + 1
            else:  # 왼쪽으로 이동
                r = mid

        return l

 

이진 탐색은 while (l <=r) 로 고정해서 푸는것이..

안헷갈리므로..

그냥 풀이 1)으로..