문제 소개
정렬되어 있던 배열이 알 수 없는 피벗(pivot) 지점을 기준으로 회전되어 있다고 가정해 봅시다. 이처럼 회전된 배열 안에서 최댓값을 찾아야 합니다. 예를 들어 배열이 [3,4,5,1,2]와 같다면 출력 결과는 5가 됩니다.
배열의 모든 요소를 하나씩 순회하는 O(n) 방식 대신, 이진 탐색(Binary Search)을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.
해결 접근 방법
low := 0, high := 배열의 마지막 인덱스, n := 배열의 크기, ans := 0으로 초기화합니다.
low <= high를 만족하는 동안 반복합니다.
mid := low + (high − low) / 2로 중간 인덱스를 계산합니다.
arr[low] < arr[mid]라면, ans를 ans와 arr[low] 중 더 큰 값으로 갱신한 뒤 low := mid + 1로 이동합니다.
그 외에 arr[high] > arr[mid]라면, ans를 ans와 arr[mid] 중 더 큰 값으로 갱신한 뒤 high := mid − 1로 이동합니다.
그 외에 low = mid라면, ans를 ans와 arr[low] 중 더 큰 값으로 갱신한 뒤 low := mid + 1로 이동합니다.
그 외에 high = mid라면, ans를 ans와 arr[high] 중 더 큰 값으로 갱신한 뒤 high := mid − 1로 이동합니다.
반복이 끝나면 ans를 반환합니다.
핵심 아이디어는 매 단계마다 배열에서 정렬된 구간을 확인해 해당 구간의 최댓값을 ans에 기록하고, 최댓값이 존재할 가능성이 남은 나머지 구간으로 탐색 범위를 계속 좁혀가는 것입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector <int>& arr, int low, int high){
if(low == high){
return arr[low];
}
int mid = low + (high - low) / 2;
int ans = 0;
if(arr[low] < arr[mid]){
ans = max(arr[low], search(arr, mid, high));
}
else if (arr[high] > arr[mid]){
ans = max(arr[mid], search(arr, low, mid));
}
else if(arr[low] == arr[mid]){
ans = max(arr[low], search(arr, low + 1, high));
}
else if(arr[high] == arr[mid]){
ans = max(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMax(vector<int>& nums) {
return search(nums, 0, nums.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {4,5,5,5,6,8,2,3,4};
cout <<(ob.findMax(v));
}입력
[4,5,5,5,6,8,2,3,4]
출력
8
동작 원리 살펴보기
예제 입력 [4,5,5,5,6,8,2,3,4]는 원래 [2,3,4,4,5,5,5,6,8]로 정렬되어 있던 배열이 특정 피벗을 기준으로 회전된 형태입니다. 재귀적 이진 탐색은 각 호출마다 구간의 양쪽 끝 값을 ans와 비교해 갱신하면서 탐색 범위를 줄여나가고, 최종적으로 배열 전체의 최댓값인 8을 반환합니다.
시간 복잡도 및 공간 복잡도
매 호출마다 탐색 범위가 절반으로 줄어들기 때문에 평균 시간 복잡도는 O(log n)입니다. 다만 중복 요소가 많아 low = mid 또는 high = mid 상황이 자주 발생하면 탐색 범위가 한 칸씩만 줄어들 수 있어, 최악의 경우 O(n)까지 증가할 수 있습니다. 공간 복잡도는 재귀 호출 스택으로 인해 O(log n)입니다.