문제 개요
배열 A가 주어졌을 때, 이를 왼쪽(left)과 오른쪽(right) 두 개의 부분 배열로 분할해야 합니다. 이때 분할 결과는 다음 세 가지 조건을 모두 만족해야 합니다.
- 왼쪽 부분 배열의 모든 원소는 오른쪽 부분 배열의 모든 원소보다 작거나 같아야 합니다.
- 왼쪽과 오른쪽 부분 배열은 모두 비어 있지 않아야 합니다.
- 왼쪽 부분 배열의 크기는 가능한 한 가장 작아야 합니다.
목표는 이러한 분할이 이루어진 후 왼쪽 부분 배열의 길이를 구하는 것입니다. 문제에서는 이러한 분할이 항상 존재한다고 보장합니다.
예를 들어 입력이 [5,0,3,8,6]이라면 출력은 3입니다. 왼쪽 배열은 [5,0,3]이 되고, 오른쪽 배열은 [8,6]이 됩니다. 왼쪽 배열의 최댓값(5)이 오른쪽 배열의 최솟값(6)보다 작거나 같으므로 조건을 만족하며, 더 짧은 왼쪽 배열로는 조건을 충족할 수 없습니다.
해결 알고리즘
이 문제는 접두사 최댓값(prefix maximum)과 접미사 최솟값(suffix minimum)을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 풀이 단계는 다음과 같습니다.
- n := 배열 A의 크기로 설정하고, 크기가 n인 배열 maxx를 생성합니다.
- minVal := A의 마지막 원소로 초기화합니다.
- maxx[0] := A[0]으로 설정합니다.
- i를 1부터 n-1까지 반복하며 maxx[i] := max(A[i], maxx[i-1])를 계산합니다. 즉, maxx[i]에는 인덱스 0부터 i까지의 최댓값이 저장됩니다.
- ans := 배열 A의 크기 - 1로 초기화합니다.
- i를 n-1부터 1까지 역순으로 반복합니다.
- minVal := min(minVal, A[i])로 갱신하여 인덱스 i부터 끝까지의 최솟값을 추적합니다.
- 만약 minVal >= maxx[i-1]이라면, 인덱스 i에서 분할했을 때 조건이 성립하므로 ans := i로 갱신합니다.
- 반복이 끝나면 ans를 반환합니다. 역순으로 탐색하기 때문에 마지막에 남은 값이 가장 작은 유효한 분할 지점입니다.
예제 코드
다음 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int partitionDisjoint(vector <int>& A) {
int n = A.size();
vector <int> maxx(n);
int minVal = A[n - 1];
maxx[0] = A[0];
for(int i = 1; i < n; i++){
maxx[i] = max(A[i], maxx[i - 1]);
}
int ans = A.size() - 1;
for(int i = n - 1; i >= 1; i--){
minVal = min(minVal, A[i]);
if(minVal >= maxx[i - 1]){
ans = i;
}
}
return ans;
}
};
main(){
vector<int> v1 = {5,0,3,8,6};
Solution ob;
cout << (ob.partitionDisjoint(v1));
}
입력
[5,0,3,8,6]
출력
3
정리
이 알고리즘은 배열을 앞에서부터 스캔하며 각 위치까지의 최댓값을 미리 계산해 두고, 뒤에서부터 스캔하며 각 위치 이후의 최솟값과 비교하는 방식으로 동작합니다. 두 값을 비교하여 분할 조건이 성립하는 가장 작은 인덱스를 찾으면 되므로, 전체 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다. 단 한 번의 순회로 정답을 구할 수 있는 효율적인 접근 방식입니다.