[Leet Code 내 맘대로 풀이] 162. Find Peak Element

문제 설명

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

자세한 문제는 위 링크 참고. 주어진 리스트에서 인접한 수보다 큰 수의 인덱스를 찾는 문제다. 예를들면 12343 이라는 인풋이 있으면 리턴은 3이 되겠다. 왜냐하면 3번째 원소인 4의 양 옆에 4보다 큰 수가 없기 때문이다.

첫번째 풀이

그저 가장 큰 값을 찾으면 된다. max 함수를 통해 큰 값을 찾으면 어차피 양옆에는 당연히 작은애들만 있을 거다. 어차피 문제 자체가 peak 인거 하무거나 하나만 답으로 주면 되기 때문에 이렇게 해도 된다.

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

두번째 풀이

바이너리 서치로도 풀 수 있다. 사실 첨에 이걸 어떻게 바이너리 서치로 풀지라고 생각했는데, 생각해보니 mid 값보다 큰 값을 따라가다 보면 max 값이든 변곡점이든 찾을 수 있을 것이다. 아래 풀이는 리트 코드 홈페이지의 누군가의 솔루션을 따라서 적은 코드다.

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