latentspace.world

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

문제 소개

이 문제는 산 배열(Mountain Array)에서 피크(peak) 요소의 인덱스를 찾는 문제이다.

산 배열(Mountain Array)이란 값이 증가하다가 피크에 도달한 후 감소하는 배열을 의미한다.

이 문제의 요지는 로그 시간 복잡도로 해결해야 하는 점이 중요한 제약 조건이다.

문제 조건

배열 길이: 3 ≤ arr.length ≤ 10^5
배열 요소 값: 0 ≤ arr[i] ≤ 10^6
입력 배열은 항상 산 배열(값이 증가했다가 감소하는 형태)
시간 복잡도: O(log n)로 해결해야 함

예시

입력:

[0,1,0]

출력:

입력:

[0,2,1,0]

출력:

입력:

[0,10,5,2]

출력:

문제 해법

풀이는 두 가지다.

방법 1: 선형 탐색 (O(n))

가장 단순한 접근 방법은 배열을 처음부터 끝까지 순회하면서 증가하다가 감소하는 지점을 찾아내면 된다.

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        for i in range(1, len(arr) - 1):
            if arr[i - 1] < arr[i] > arr[i + 1]:
                return i

하지만 이 방식은 최악 경우 O(n) 시간이 소요되므로 문제의 요구 사항인 O(log n)을 충족하지 못한다는 문제가 있다.

방법 2: 이진 탐색 (O(log n))

이진 탐색을 활용하면 O(log n) 시간 복잡도를 달성할 수 있다. 핵심 아이디어는 배열을 증가-감소 두 갈래로 나눌 수 있다는 점이다.

상승 중(피크의 왼쪽)
하강 중(피크의 오른쪽)

배열의 중간 지점(mid)과 그 다음 지점(mid+1)을 비교하여

arr[mid] < arr[mid+1]이면 상승 중이므로 피크는 오른쪽에 있다는 의미.
arr[mid] > arr[mid+1]이면 하강 중이므로 피크는 현재 위치이거나 왼쪽에 있다는 의미이다.

이와 같이 배열의 증가-감소를 판단하여 탐색 범위를 계속 절반으로 줄여나가면 결국 최고점에 도달하게 된다.

최종 구현

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left = 0
        right = len(arr) - 1

        peak = left

        while left <= right:
            mid = (right - left) // 2 + left
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            elif arr[mid - 1] > arr[mid]:
                right = mid - 1
            else:
                peak = mid
                break

        return peak

오버플로우를 방지하기 위해 mid = (left + right) // 2 대신 mid = left + (right - left) // 2를 사용한다.

Python 에서는 전혀 문제가 없지만.. C 계열이나 Java 에서는 문제가 될 수 있을 것 같다.

성능 분석

시간 복잡도

기본적인 이진 탐색 알고리즘을 사용하므로 시간 복잡도는 O(log n)이다.
각 단계에서 배열의 검색 범위가 절반으로 줄어들기 때문
- T(n) = T(n/2) + O(1) (n ≥ 2)
- T(n) = O(1) (n = 1)

공간 복잡도

공간 복잡도는 O(1) 이다.
- 추가적인 자료구조를 사용하지 않으므로..