C++에서 배열을 개별적으로 정렬할 수 있는 최대 파티션 수 구하기

문제 소개

원소가 모두 0부터 N-1 범위 안에 있는 크기 N의 배열이 주어집니다. 배열은 정렬되어 있지 않으며, 우리의 목표는 이 배열을 여러 개의 파티션(구간)으로 나눈 뒤 각 파티션을 개별적으로 정렬하고 다시 이어 붙였을 때 전체가 정렬된 배열이 되도록 만들 수 있는 파티션의 최대 개수를 구하는 것입니다.

각 파티션은 내부 원소들이 정렬되어 있지 않은 상태로 선택됩니다. 0부터 N-1까지의 숫자로 이루어진 배열이 정렬된 상태라면 각 원소는 자신의 값과 동일한 인덱스에 위치하게 됩니다. 즉, Arr[i] = i가 성립합니다.

이 문제는 각 원소를 자신의 왼쪽에 있는 값들 중 최댓값과 비교하는 방식으로 해결할 수 있습니다. 탐색하면서 지금까지의 최댓값(maxx)을 계속 추적하다가, 어느 인덱스 i에서 maxx == i가 되는 순간이 오면 그 위치까지의 모든 원소를 하나의 파티션으로 묶을 수 있습니다. 왼쪽 원소들은 모두 더 작고 오른쪽 원소들은 모두 더 크기 때문입니다. 이후에는 오른쪽 나머지 원소들에 대해 같은 절차를 반복하며 파티션을 계속 나눠 줍니다.

예시를 통해 자세히 살펴보겠습니다.

예시 1

입력 − Arr[] = { 0, 3, 2, 1, 4, 5 }

출력 − 최대 파티션 수: 3

설명 − 인덱스 0부터 시작하여 max = Arr[0] = 0으로 설정합니다.
인덱스 0~3 사이에서 최댓값은 3입니다. 인덱스 i = 3에 도달했을 때 maxx == i가 성립하므로 첫 번째 파티션은 [0, 3, 2, 1]입니다.
인덱스 4에서 최댓값은 4이고, i = 4에서 maxx == i가 성립하므로 두 번째 파티션은 [4]입니다.
인덱스 5에서 최댓값은 5이고, i = 5에서 maxx == i가 성립하므로 세 번째 파티션은 [5]입니다.
결국 총 3개의 파티션 [0, 3, 2, 1], [4], [5]로 나눌 수 있으며, 각각을 정렬한 뒤 이어 붙이면 됩니다.

예시 2

입력 − Arr[] = { 5, 4, 3, 2, 1, 0 }

출력 − 최대 파티션 수: 1

설명 − 인덱스 0부터 시작하여 max = Arr[0] = 0으로 설정합니다.
인덱스 0~5 사이에서 최댓값은 5입니다. 인덱스 i = 5에 도달했을 때 비로소 maxx == i가 성립하므로 전체 배열이 하나의 파티션 [5, 4, 3, 2, 1, 0]이 됩니다.

알고리즘 접근 방식

0부터 N 범위의 숫자로 초기화된 정수 배열 Num[]을 사용합니다.
partitions(int arr[], int n) 함수는 배열과 그 길이를 매개변수로 받아, 개별적으로 정렬한 후 이어 붙였을 때 전체 배열이 정렬되도록 만들 수 있는 최대 파티션 수를 반환합니다.
초기 파티션 개수는 0, 초기 최댓값 maxx는 arr[0]으로 설정합니다.
가장 왼쪽 원소부터 모든 원소를 순회하며 현재 값이 maxx보다 큰지 확인합니다.
arr[i] > maxx가 참이면 maxx를 갱신합니다.
현재 maxx와 인덱스가 같다면(maxx == i), 인덱스 i까지의 모든 원소가 하나의 파티션에 속하므로 count를 증가시킵니다.
오른쪽 끝에 도달할 때까지 나머지 원소들에 대해 같은 과정을 반복합니다.
최종 결과인 count를 반환합니다.

이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(N)이며, 추가 메모리 사용량도 상수 수준으로 매우 효율적입니다.

C++ 코드 예시

#include <bits/stdc++.h>
using namespace std;
int partitions(int arr[], int n){
    int count = 0;
    int maxx = arr[0];
    for (int i = 0; i < n; ++i) {
        if(arr[i] > maxx)
            maxx=arr[i];
        if (maxx == i)
            count++;
    }
    return count;
}
int main(){
    int Num[] = { 2,1,0,4,5,3 };
    int len = 6;
    cout <<"Maximum partitions that can be sorted: "<<partitions(Num, len);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Maximum partitions that can be sorted: 2

배열 { 2, 1, 0, 4, 5, 3 }의 경우 인덱스 2에서 maxx == 2가 되어 첫 번째 파티션 [2, 1, 0]이 만들어지고, 이후 인덱스 5에서 maxx == 5가 되어 두 번째 파티션 [4, 5, 3]이 만들어집니다. 따라서 총 2개의 파티션으로 나눌 수 있으며, 각각을 정렬한 뒤 이어 붙이면 전체 배열이 정렬된 상태가 됩니다.