162. Find Peak Element

Find Peak Element - LeetCode

정수 배열이 주어진다.

 

주어진 배열을 산의 높이라고 생각하고 Peek의 index를 반환하는 문제다.

산에는 여러 개의 Peek가 있을 수 있고 이런 경우는 조건에 해당하는 여러 개의 index 중 하나를 반환하면 된다.

 

예시

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.

 

1. 선형 탐색

from typing import *


class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if not nums:
            return None
        if len(nums) == 1:
            return 0
        nums.append(-float("inf"))
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i
        return len(nums) - 1

문제에서 원하는 index가 가장 높은 index도 아니고, 그냥 Peek 조건에 맞는 index 중 아무거 나이기 때문에 현재 지점이 다음 지점보다 높으면 그 index를 반환하면 된다.

 

여기서 시간 복잡도를 줄여서 지수 레벨로 내리려면 어떻게 해야 할까?

 

2. 이진 탐색을 이용한 최적해

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

최적해 문제는 대부분 다음과 같은 형태를 띤다.

1. 가능한 값의 범위를 정한다.
2. 그 범위의 중간값이 우리가 원하는 값인지 판단한다.
3. 그렇지 않다면 범위를 조정하고 이를 계속 반복한다.

우리가 원하는 index 값의 범위를 left, right로 정한다. 그 뒤 left와 right의 중간인 mid를 얻어 이 mid가 우리가 원하는 조건인 mid+1이 가리키는 값이 mid가 가리키는 값보다 작은 지를 판단한다.

만약 그렇다면 right를 mid로 옮기고 그렇지 않다면 left를 mid+1로 옮긴다.

 

여기서 left, right을 재할당해주는 부분이 어려운데 상황을 한번 생각해보면 어디에 +1을 해줘야 할지, 범위를 어떻게 해야 할지 판단하는데 도움이 된다.

 

이진 탐색은 정렬된 배열에서 사용할 수 있는 게 아닌가요?라는 질문을 할 수 있는데, 여기서 이진 탐색의 대상은 산의 높이, 즉 배열의 값이 아니라 배열의 인덱스이고, 인덱스는 0부터 오름차순으로 정렬되어있기 때문에 사용할 수 있다.

 

포스팅할만한 문제를 오랜만에 풀었다.