피크(Peak) 요소란?
배열에서 피크 요소란 자신의 바로 옆에 있는 이웃 요소들보다 값이 큰 원소를 의미합니다. 입력 배열 nums가 주어지며, 모든 i에 대해 nums[i] ≠ nums[i+1]이라는 조건이 보장됩니다. 우리가 할 일은 피크 요소를 하나 찾아 해당 인덱스를 반환하는 것입니다.
배열에는 피크 요소가 여러 개 존재할 수 있으며, 이 경우 그중 어떤 피크 요소의 인덱스를 반환해도 정답으로 인정됩니다. 경계 처리를 단순하게 하기 위해 nums[-1] = nums[n] = -∞라고 가정합니다. 즉, 배열의 양 끝 바깥에는 마이너스 무한대가 있다고 생각하면 됩니다.
예를 들어 배열이 [1, 2, 1, 3, 5, 6, 4]라면 피크 요소는 인덱스 1의 값 2 또는 인덱스 5의 값 6입니다.
접근 방법: 이진 탐색(Binary Search)
모든 요소를 순회하는 선형 탐색으로도 피크를 찾을 수 있지만, 이진 탐색을 활용하면 O(log n) 만에 해결할 수 있습니다. 배열이 정렬되어 있지 않아도 괜찮습니다. 중간 지점(mid)의 이웃과 비교해 어느 쪽에 더 큰 값이 있는지만 판단하고, 항상 값이 커지는 방향으로 이동하면 반드시 피크에 도달하기 때문입니다.
알고리즘 단계
- low := 0, high := 배열의 마지막 인덱스로 초기화합니다.
- low < high를 만족하는 동안 다음을 반복합니다.
- mid := low + (high − low + 1) // 2
- mid − 1 ≥ 0 이고 nums[mid − 1] ≤ nums[mid]라면 오른쪽에 피크가 존재하므로 low := mid
- 그렇지 않으면 왼쪽에 피크가 존재하므로 high := mid − 1
- 반복문이 종료되면 low가 곧 피크 요소의 인덱스이므로 이를 반환합니다.
파이썬 구현 예제
class Solution(object):
def findPeakElement(self, nums):
low = 0
high = len(nums) - 1
while low < high:
mid = low + (high - low + 1) // 2
if mid - 1 >= 0 and nums[mid - 1] <= nums[mid]:
low = mid
else:
high = mid - 1
return low
ob1 = Solution()
print(ob1.findPeakElement([15, 35, 85, 96, 5, 6, 8, 12]))
입력
[15, 35, 85, 96, 5, 6, 8, 12]
출력
3
실행 결과인 3은 배열에서 최댓값인 96의 인덱스입니다. 96은 양옆 요소인 85와 5보다 크므로 유효한 피크 요소입니다.
복잡도 분석
- 시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어듭니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 두 개의 포인터만 사용합니다.