문제 이해하기
정수 배열 arr가 주어졌을 때, 이 배열을 여러 개의 파티션(청크)으로 나누고 각 파티션을 개별적으로 정렬한 후 다시 이어 붙이면 하나의 정렬된 배열이 됩니다. 우리가 구해야 할 것은 바로 만들 수 있는 파티션의 최대 개수입니다.
예를 들어 입력이 [3,2,4,5,5]라면 출력은 4입니다. [3,2], [4], [5], [5]와 같이 네 개의 파티션으로 나누면, 각각을 정렬한 뒤 이어 붙였을 때 [2,3,4,5,5]가 되어 전체 배열이 정렬 상태를 유지하기 때문입니다.
해결 접근 방식
이 문제의 핵심 아이디어는 배열을 나눌 수 있는 지점을 판별하는 것입니다. 어떤 인덱스 i를 기준으로 볼 때, 왼쪽 구간의 최댓값이 오른쪽 구간의 최솟값보다 작거나 같다면 그 경계에서 나누더라도 전체 정렬 결과에는 영향을 주지 않습니다.
구체적인 풀이 단계는 다음과 같습니다.
- 카운터
cnt를 1로 초기화하고, 배열 크기를n으로 설정합니다. - 왼쪽에서 오른쪽으로 순회하며, 각 인덱스까지의 최댓값을 저장하는
maxOfLeft배열을 만듭니다. - 오른쪽에서 왼쪽으로 순회하며, 각 인덱스부터 배열 끝까지의 최솟값을 저장하는
minOfRight배열을 만듭니다. - 인접한 두 구간을 비교하면서,
minOfRight[i+1]이maxOfLeft[i]보다 크거나 같으면 해당 경계에서 분할이 가능하므로cnt를 1 증가시킵니다. - 모든 경계를 확인한 후
cnt를 반환합니다.
이 방식은 배열을 두 번 순회해 전처리하고 한 번 더 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int cnt = 1;
int n = arr.size();
vector<int> maxOfLeft(n);
vector<int> minOfRight(n);
maxOfLeft[0] = arr[0];
for (int i = 1; i < n; i++)
maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
minOfRight[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
minOfRight[i] = min(minOfRight[i + 1], arr[i]);
for (int i = 0; i < n - 1; i++) {
if (minOfRight[i + 1] >= maxOfLeft[i])
cnt++;
}
return cnt;
}
};
main(){
Solution ob;
vector<int> v = {3,2,4,5,5};
cout << (ob.maxChunksToSorted(v));
}
입력
{3,2,4,5,5}출력
4
마무리
이 알고리즘은 누적 최댓값과 누적 최솟값이라는 두 개의 보조 배열만 활용해 분할 지점을 빠르게 찾아냅니다. 중복 원소가 있어도 >= 조건 덕분에 올바르게 처리할 수 있으며, 코딩 테스트나 면접에서 자주 등장하는 배열 분할 문제의 대표적인 풀이 패턴이니 꼭 익혀두시길 권합니다.