LeetCode 852. Peak Index in a Mountain Array

LeetCode 852. Peak Index in a Mountain Array

🗓️ Daily LeetCoding Challenge July, Day 25

(23.07.25) LeetCode에서는 일명 Daily Challenge를 제공하는데, 하루에 하나씩 풀어나가면 다양한 알고리즘 문제들을 풀어볼 수 있어서 유익하다. 보통 다른 문제들은 Editoral 부분이 잠금되어있어 Premium User가 아니면 읽지 못하는데, Daily Challenge만큼은 공개되어 자신의 풀이와 비교해볼 수 있다. LeetCode에 입문한지 이제 겨우 3일이지만, 다른 알고리즘 사이트에 비해서 체계가 확실히 잘 잡혀있어서 유저들에게 매우 편리하게 다가온다.

이번 문제는 배열의 증가하다가 감소하는 수열의 극값의 index을 구하는 문제다. 보자마자 이분탐색(binary-search) 알고리즘을 사용해야겠다고 생각이 들었다. 문제 조건에서도 O(logn) 시간 복잡도를 사용하라고 제시되어있기에 확신을 가지고 문제를 풀었다.

나의 풀이

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        result = self.binary_search(arr, 0, len(arr)-1)
        return result

    # binary search
    def binary_search(self, arr, start, end):
        while start < end:
            mid = start + (end-start)//2
            if arr[mid-1] < arr[mid] < arr[mid+1]:
                start = mid
            elif arr[mid-1] > arr[mid] > arr[mid+1]:
                end = mid
            else:
                return mid
        return -1

이 문제 한정해서는 이런 풀이도…

이 문제같은 경우 매우 친절하게도 아주 이상적인 배열만을 제공한다. 따라서 산의 꼭대기에 해당하는 숫자가 곧 최대값이라 다음과 같이 풀수도 있다. 하지만, 꼭대기가 여러개인 수열이나 꼭대기가 평평한 수열(최댓값이 여러개)의 경우 적용이 힘들기에 추천하진 않는다. 일반화가 어렵기에 이런 풀이는 short coding에는 도움이 되지만 권하진 않는다.

class Solution:
    def peakIndexInMountainArray(self, arr: list[int]) -> int:
        return arr.index(max(arr))

여담

확실히 백준에 비해서 LeetCode는 C++ 친화적(?) 플랫폼인 듯 하다. 아무래도 오랬동안 알고리즘을 공부하셨던 분들은 C나 C++로 시작하셨던 분들이 많으시니까 사용층이 두툼해서 그런 경향이 생기는 것 같다. Solution의 품질도 Python보다는 C++이 훨씬 유익한 경우가 많은데, 그냥 C++ 공부해서 알고리즘 언어를 바꿔볼까 생각중이다.