이 문제는 배열 arr[]을 K개의 연속된 부분 배열로 나눈 뒤, 각 부분 배열의 최솟값들 가운데 최댓값이 가장 커지도록 만들 때 그 값이 얼마가 될 수 있는지 구하는 것입니다.
문제 예시
입력
arr[] = {2, 8, 4, 3, 9, 1, 5}, K = 3
출력
9
설명 − 배열을 3개의 연속 부분 배열로 나누면 {2, 8, 4, 3}, {9}, {1, 5}가 됩니다.
각 부분 배열의 최솟값은 차례대로 2, 9, 1입니다.
이 세 값 중 최댓값은 9입니다.
입력
arr[] = {8, 4, 1, 9, 11}, K = 1
출력
1
설명 − K가 1이면 배열 전체가 하나의 부분 배열이 되므로, 그 안에서의 최솟값인 1이 곧 결과가 됩니다.
풀이 접근 방법
이 문제는 K의 값에 따라 다음의 세 가지 경우로 나누어 생각할 수 있습니다.
경우 1 − K = 1
배열 전체가 하나의 부분 배열이 되므로, 배열 내 최솟값이 곧 정답입니다.경우 2 − K ≥ 3
부분 배열이 3개 이상이면 최댓값 원소 하나만을 담은 부분 배열을 따로 만들 수 있습니다. 이 부분 배열의 최솟값은 곧 배열 전체의 최댓값이 되므로, 정답은 항상 배열의 최댓값입니다.경우 3 − K = 2
가장 까다로운 경우입니다. 배열을 두 부분으로 나누는 모든 분할 지점을 고려해야 하므로, 접두사(prefix) 최솟값 배열과 접미사(suffix) 최솟값 배열을 미리 계산해 둡니다. 그런 다음 각 인덱스 i에 대해 아래 식으로 최댓값을 갱신합니다.MaxValue = max(MaxValue, max(i까지의 접두사 최솟값, i+1부터의 접미사 최솟값))
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
/* K개의 연속 부분 배열의 최솟값 중 최댓값의 최대값을 구하는 함수 */
int Max(const int* arr, int size, int K){
int Max = INT_MIN;
int Min = INT_MAX;
// 배열의 최댓값과 최솟값 구하기
for (int i = 0; i < size; i++){
Min = min(Min, arr[i]);
Max = max(Max, arr[i]);
}
// K = 1이면 최솟값 반환
if (K == 1){
return Min;
}
// K ≥ 3이면 최댓값 반환
else if (K >= 3){
return Max;
}
// K = 2이면 접두사·접미사 최솟값 활용
else{
// 접두사 및 접미사 최솟값을 저장할 배열
int Left[size], Right[size];
Left[0] = arr[0];
Right[size - 1] = arr[size - 1];
// 접두사 최솟값 계산
for (int i = 1; i < size; i++){
Left[i] = min(Left[i - 1], arr[i]);
}
// 접미사 최솟값 계산
for (int i = size - 2; i >= 0; i--){
Right[i] = min(Right[i + 1], arr[i]);
}
int MaxValue = INT_MIN;
// 가능한 최댓값 구하기
for (int i = 0; i < size - 1; i++){
MaxValue = max(MaxValue, max(Left[i], Right[i + 1]));
}
return MaxValue;
}
}
int main(){
int arr[] = {9, 4, 12, 5, 6, 11};
int size = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << "K개의 연속 부분 배열의 최솟값 중 최댓값의 최대화 결과: "
<< Max(arr, size, K);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 나옵니다.
K개의 연속 부분 배열의 최솟값 중 최댓값의 최대화 결과: 11
복잡도 분석
K = 1 또는 K ≥ 3인 경우에는 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)입니다. K = 2인 경우에도 접두사·접미사 최솟값 배열을 각각 한 번씩 계산한 뒤 마지막으로 한 번 더 순회하므로 역시 O(n)이며, 추가 배열 공간이 필요하므로 공간 복잡도는 O(n)입니다.