[Leetcode] 162. Find Peak Element (python)

#1.  문제

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

Find Peak Element - LeetCode

 

 

정수 배열 nums가 주어질 때 인접 요소보다 더 큰 peak 요소를 찾는 문제

다수의 peak이 발생하는 경우 어느 하나 인덱스만 반환해도 상관없다.

참고로 모든 nums 요소는 다음 조건을 만족하며, 풀이는 O(logN)으로 풀이해야 한다.

nums[i] != nums[i + 1] 

 

Input: 
nums = [1, 2, 1, 3, 5, 6, 4]

Output: 
1 or 5

Explanation:

idx = 1:
2는 양 옆의 요소보다 크므로 peak

idx = 5:
6은 양 옆의 요소보다 크므로 peak

 

 

---

#2.  풀이

 

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        def search(left: int, right: int):

            mid = (left + right) // 2

            if (mid == 0 or nums[mid] >= nums[mid - 1]) and (
                mid == len(nums) - 1 or nums[mid] >= nums[mid + 1]
            ):
                return mid
            elif nums[mid] < nums[mid + 1]:
                return search(mid + 1, right)
            else:
                return search(left, mid - 1)

        left, right = 0, len(nums) - 1

        return search(left, right)

 

문제와 요구사항에서 이진탐색 풀이의 느낌이 나긴 했는데, 문제를 꼼꼼하게 읽지 않아 처음에 꽤 힘들었던 문제다.이진탐색 + 재귀 형태로 풀었다.이진탐색을 위해 배열의 중간값을 찾아주고 재귀의 종료조건은 문제의 요구사항대로 양 옆 요소보다 큰 경우으로 상정한다.

 

현재 중간값보다 바로 오른쪽 값이 더 크다면 바로 오른쪽 값 혹은 그 이후의 값들이 peak가 될 수 있으므로,
나누어진 오른쪽 값들에서 peak를 다시 찾는 과정을 반복하고, 그 반대의 경우도 같은 방식으로 반복한다.

재귀가 일어날 때마다 배열의 크기가 반씩 줄어드므로 시간복잡도는 O(logN)이다.