C++로 회전 정렬 배열의 회전 횟수 구하기: 선형 탐색부터 이진 탐색까지

문제 이해

정렬되어 있던 배열이 어느 지점에서 회전된 형태, 즉 회전 정렬 배열(rotated sorted array)이 주어졌다고 가정해 봅시다. 해야 할 일은 이 배열을 원래의 정렬 상태로 되돌리기 위해 필요한 최소 회전 횟수를 구하는 것입니다. 단, 회전은 오른쪽 끝 요소를 왼쪽으로 옮기는 방향(오른쪽 → 왼쪽)으로 수행한다고 가정합니다.

예를 들어 배열이 {15, 17, 1, 2, 6, 11}이라면, 두 번 회전했을 때 {1, 2, 6, 11, 15, 17}이 되어 완전히 정렬됩니다. 따라서 이 경우 정답은 2입니다.

핵심 아이디어

논리는 매우 간단합니다. 배열을 자세히 관찰해 보면 회전 횟수는 최솟값 요소의 인덱스와 같다는 사실을 알 수 있습니다. 위 예제에서 최솟값은 1이고 그 인덱스는 2이므로, 배열에서 최솟값의 위치만 찾으면 그 값이 곧 필요한 회전 횟수가 됩니다.

C++ 구현: 선형 탐색 (O(n))

가장 직관적인 방법은 배열을 한 번 순회하면서 최솟값의 인덱스를 찾는 것입니다. 시간 복잡도는 O(n)입니다.

#include <iostream>
using namespace std;

int getMinIndex(int arr[], int n){
    int index = 0;
    for(int i = 1; i<n; i++){
        if(arr[i] < arr[index]){
            index = i;
        }
    }
    return index;
}

int countNumberOfRotations(int arr[], int n){
    return getMinIndex(arr, n);
}

int main() {
    int arr[] = {15, 17, 1, 2, 6, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Number of required rotations: " << countNumberOfRotations(arr, n);
}

출력 결과

Number of required rotations: 2

개선: 이진 탐색 활용 (O(log n))

배열이 한 번 회전된 정렬 배열이라는 구조적 특성을 활용하면 이진 탐색으로 최솟값의 위치를 훨씬 빠르게 찾을 수 있습니다. 중간 요소와 마지막 요소를 비교해 최솟값이 어느 쪽 절반에 속하는지 판단하는 방식으로, 요소가 중복 없이 정렬되어 있다는 전제에서 시간 복잡도를 O(log n)까지 줄일 수 있습니다.

#include <iostream>
using namespace std;

int countRotations(int arr[], int n){
    int low = 0, high = n - 1;
    while(low < high){
        int mid = low + (high - low) / 2;
        if(arr[mid] > arr[high]){
            low = mid + 1;  // 최솟값은 오른쪽 절반에 있음
        }else{
            high = mid;     // 최솟값은 왼쪽 절반에 있음
        }
    }
    return low;
}

int main() {
    int arr[] = {15, 17, 1, 2, 6, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Number of required rotations: " << countRotations(arr, n);
}

마무리

회전 정렬 배열의 회전 횟수는 곧 최솟값의 인덱스라는 점이 이 문제의 핵심입니다. 정렬 보장이 없는 일반 배열이라면 선형 탐색(O(n))이 유일한 선택이지만, 회전 정렬 배열처럼 구조적 힌트가 있는 경우에는 이진 탐색(O(log n))을 적용해 탐색 성능을 크게 향상시킬 수 있습니다.