C++로 구하는 정렬 가능한 최대 청크 개수

문제 개요

배열 arr이 [0, 1, ..., arr.length - 1]의 순열(permutation)로 주어졌다고 가정해 봅시다. 이 배열을 여러 개의 "청크(chunk)", 즉 부분 구간으로 나눈 뒤, 각 청크를 개별적으로 정렬하고 다시 이어 붙였을 때 전체가 정렬된 배열이 되도록 해야 합니다.

예를 들어 배열이 [1, 0, 2, 3, 4]라면 출력은 4가 됩니다. 배열을 [1, 0]과 [2, 3, 4] 두 개의 파티션으로 나눌 수도 있지만, [1, 0], [2], [3], [4]처럼 네 개로 나누는 것도 가능합니다. 이렇게 만들 수 있는 청크의 최대 개수가 4이므로 정답은 4입니다.

그렇다면 우리가 만들 수 있는 청크의 최대 개수는 어떻게 구할 수 있을까요?

접근 방법

핵심 아이디어는 간단합니다. 배열이 0부터 n-1까지의 순열이므로, 인덱스 i까지 등장한 값들의 최댓값이 정확히 i

다음 단계에 따라 문제를 해결할 수 있습니다.

• ans := 0, maxVal := -inf, n := arr의 크기로 초기화합니다.
• i를 0부터 n-1까지 반복하면서:
  • maxVal을 arr[i]와 기존 maxVal 중 큰 값으로 갱신합니다.
  • maxVal == i라면 ans를 1 증가시킵니다.
• 최종적으로 ans를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

아래 C++ 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int ans = 0;
        int minVal = INT_MAX;
        int n = arr.size();
        int maxVal = INT_MIN;
        for(int i = 0; i < n; i++){
            maxVal = max(arr[i], maxVal);
            if(maxVal == i){
                ans++;
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,0,2,3,4};
    cout << (ob.maxChunksToSorted(v));
}

입력

[1,0,2,3,4]

출력

4

동작 원리 살펴보기

입력 [1, 0, 2, 3, 4]로 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.

• i = 0: maxVal = 1, 1 ≠ 0 → 청크 없음
• i = 1: maxVal = max(0, 1) = 1, 1 == 1 → 청크 1개 확정 ([1, 0])
• i = 2: maxVal = max(2, 1) = 2, 2 == 2 → 청크 2개 확정 ([2])
• i = 3: maxVal = max(3, 2) = 3, 3 == 3 → 청크 3개 확정 ([3])
• i = 4: maxVal = max(4, 3) = 4, 4 == 4 → 청크 4개 확정 ([4])

최종 결과는 4로, 예상한 답과 일치합니다. 이 방식은 현재 위치까지의 최댓값이 해당 인덱스와 일치하는 순간마다 경계를 만들면, 각 청크를 따로 정렬했을 때 전체 배열이 자동으로 정렬된다는 사실에 기반합니다.