LeetCode [ 162 | Python ] Find Peak Element

문제

https://leetcode.com/problems/find-peak-element/description/?envType=study-plan-v2&envId=top-interview-150

주어진 배열 nums 에서 가장 큰 값을 찾아내야 하는 최대값 문제.

풀이

시도 1

실행시간 : 28ms
메모리 : 13.5MB

nums의 길이가 길지 않아서 혹시 싶어 시도해 보았던 코드.
의외로 통과가 됐다.(O(log n) 안에 끝내야 한댔는데..)

파이썬의 max 는 선형 탐색을 수행하기 때문에 최악의 경우 O(n**2)의 시간 복잡도가 걸리는 코드이다.

정말 직관적으로 함수만 사용한 코드이기 때문에, 더 효율적으로 큰 값을 찾아내고자 했다.

class Solution(object):
    def findPeakElement(self, nums):

        return nums.index(max(nums)) 

개선

실행시간 : 23ms 메모리 : 13.2MB

O(log n) 이라는 시간 복잡도를 맞춰야하기 때문에 떠올랐던 건 이분탐색이었다.
이분 탐색은 정렬되어 있는 배열에서만 사용해야한다고 알고 있었지만, 중간값과 그 주위의 값을 이용하면 충분히 이용가능하다는 것을 깨달았다.
peak 라는 단어를 통해 힌트를 얻었다.

1. 이분탐색을 수행하기 위한 변수 l(범위 시작 값), r(범위 끝 값)을 초기화한다.
2. 이분탐색을 수행한다.
   1. 중간값을 기준으로 수행한다.
   2. 중간 값과 그 오른쪽에 있는 값을 비교한다.
      1. 중간값이 오른쪽에 있는 값 보다 큰 경우 r 값을 m 값으로 범위를 축소시킨다.
      2. 이외의 경우 l 값을 m + 1 값으로 확장시킨다.
3. 탐색을 마치고 난 l을 반환한다.

class Solution(object):
    def findPeakElement(self, nums):

        l, r = 0, len(nums) - 1
        
        while l < r:
            m = (l + r) // 2
            
            if nums[m] > nums[m + 1]:
                r = m
            else:
                l = m + 1
        
        return l

생각 & 정리

분명 이분탐색은 정렬되어 있는 배열에서만 사용가능하다고
알고있었는데 특정 값이 아닌 가장 작은 값, 가장 큰 값을 찾기에는 크게 무리가 없었다.

그 이유로는 기준으로 삼는 m값과 그 근처의 값을 사용했기 때문인데,
정석적인 이분탐색으로는 l과 m, m과 r사이가 작은값, 큰값들로만 이뤄져있다는 것을 약속하고 있기 때문에 풀이하기 어려웠을 것이다.

다른 문제들도 그렇지만, 이분 탐색은 특히 익숙치 않아서인지 유연한 생각이 필요한 것 같다.
어떤 값을 기준으로 삼을지, 얼마만큼 값을 감소시키고 증가시킬지 고려해야하는 점이 다소 까다롭게 느껴진다.