leetcode medium : Peak Index in a Mountain Array

https://leetcode.com/problems/peak-index-in-a-mountain-array/description/

Peak Index in a Mountain Array - LeetCode

 

Peak Index in a Mountain Array

풀기 전

예전에 비슷한 문제를 풀었던거같다. 그때는 mountain array인지 아닌지 검사하는거라서 linear time으로 풀었던거 같은데, 이번엔 조건이 살짝 달라졌다.

• 일부 정렬되어 있는 array
• O(log N) time complexity
• 주어진 array는 무조건 mountain array

누가 봐도 binary search를 하라고 대놓고 말해주고 있는거같다.

인덱스를 low와 high로 잡아놓고 mid인덱스에서 list[mid-1] < list[mid] > list[mid+1]을 만족하는지 검사하면 될거같다. 만약 list[mid-1] < list[mid] < list[mid+1]이라면 mid가 더 오른쪽에 있는 것이므로 low를 높여주면 되겠고 그 반대라면 high을 낮춰주면 되겠다.

코드 설명

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        low = 1
        high = len(arr) - 2

        while low <= high:
            mid = (low + high) // 2

            if arr[mid-1] < arr[mid] > arr[mid+1]:
                return mid
            if arr[mid-1] < arr[mid] < arr[mid+1]:
                low = mid + 1
            else:
                high = mid

        return -1

직접 돌려보지 않으면서 off by one 버그 없이 어떻게 풀지 고민했다.

시뮬레이션을 직접 돌려보면서 검증했고 한 번에 통과했다.

low = 1
high = len(arr) - 2

일단 array의 길이가 최소 3 이상이고 peak는 무조건 중간에 있어야 하므로 peak index의 하한선은 1, 상한선은 len(arr) - 2다.

while low <= high:

수많은 binary search 구현 경험 결과 while 조건에서는 equal 조건도 포함시키는게 좋다.

equal 없이 low < high로만 되어있으면 low = high인 경우에 mid가 정답인지 아닌지 어떻게 검증할 것인가?

mid = (low + high) // 2

if arr[mid-1] < arr[mid] > arr[mid+1]:
    return mid

mid를 구하고 나서 가장 먼저 해야 될 것은 정답 조건을 검사하는 것이다.

정답이 맞으면 mid를 반환한다.

if arr[mid-1] < arr[mid] < arr[mid+1]:
    low = mid + 1
else:
    high = mid

무한루프를 방지하기 위해 한쪽에선 값을 올려주고(mid+1)

한쪽에선 값을 똑같게 만들어준다 (high = mid)

이렇게 하면 while문 안에서 정답이 무조건 걸리게 된다.

return -1

정답을 못찾으면 -1을 리턴한다. 하지만 인풋 array가 무조건 mountain array이기 때문에 이 리턴문까지 실행되는 경우는 없다.

분석 및 피드백

Time Complexity는 O(log N)

Space Complexity는 O(1)

99%, 95%

코드도 지저분하지 않은 것 같고 특별히 손볼곳은 없어보인다.

하지만 항상 binary search를 어떻게 하면 버그 없이 깔끔하게 구현할 수 있을까는 고민이 된다.

솔루션 학습

Binary Search 말고도 Golden Section Search라는 알고리즘이 있다는 걸 알게됐다. 효율성에 대해서는 논란이 좀 있어서 binary search보다 무조건 낫다고 단정짓긴 힘들거같다. 로그타임인건 확실.

def peakIndexInMountainArray(self, A):
    def gold1(l, r):
        return l + int(round((r - l) * 0.382))

    def gold2(l, r):
        return l + int(round((r - l) * 0.618))
    l, r = 0, len(A) - 1
    x1, x2 = gold1(l, r), gold2(l, r)
    while x1 < x2:
        if A[x1] < A[x2]:
            l = x1
            x1 = x2
            x2 = gold1(x1, r)
        else:
            r = x2
            x2 = x1
            x1 = gold2(l, x2)
    return A.index(max(A[l:r + 1]), l)

binary search 3분의 1 버전인거같기도 하고.. 잘 모르겠다.