이 문제에서는 정수 배열 arr[]와 하나의 구간(range)이 주어지며, 우리의 과제는 주어진 구간에 속한 부분 배열이 산(mountain) 형태인지 판별하는 것입니다. 여기서 산 형태란 배열의 값이 처음에는 계속 증가하다가 어느 정점을 기준으로 다시 계속 감소하는 모양을 의미합니다.
문제 이해하기
예시를 통해 문제를 자세히 살펴보겠습니다.
입력 : arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, 구간 = [2, 7]
출력 : Yes설명 −
구간 [2, 7]에 해당하는 부분 배열 = {2, 5, 6, 7, 3, 0}
값이 먼저 증가한 후 감소하므로 산 형태입니다.해결 접근 방법
이 문제의 간단한 해결 방법은 추가 배열을 활용하는 것입니다. 배열의 각 원소에 대해 증가 구간이 끝나는 마지막 인덱스와 감소 구간이 시작되는 인덱스를 미리 계산하여 저장해 둡니다. 그런 다음 주어진 구간 [L, R]에 대해 두 값을 비교함으로써 해당 부분 배열이 산 형태를 이루는지 단 한 번의 비교만으로 빠르게 확인할 수 있습니다.
left[i]: 인덱스 i 기준으로 왼쪽 방향의 증가 수열이 유지되는 가장 왼쪽 인덱스right[i]: 인덱스 i 기준으로 오른쪽 방향의 감소 수열이 유지되는 가장 오른쪽 인덱스
이때 right[L] >= left[R] 조건을 만족하면 구간 [L, R]의 부분 배열은 산 형태입니다. 전처리 과정에 O(N)의 시간이 소요되며, 이후 각 구간 질의는 O(1)에 처리되므로 동일한 배열에 대해 여러 번의 구간 검사가 필요할 때 매우 효율적인 방법입니다.
구현 예제
아래 프로그램은 위 해결 방법의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int processArray(int arr[], int N, int left[], int right[]){
left[0] = 0;
int increasingValR = 0;
for (int i = 1; i < N; i++){
if (arr[i] > arr[i - 1])
increasingValR = i;
left[i] = increasingValR;
}
right[N - 1] = N - 1;
int decreasingValL = N - 1;
for (int i = N - 2; i >= 0; i--){
if (arr[i] > arr[i + 1])
decreasingValL = i;
right[i] = decreasingValL;
}
}
bool isMountainSubArray(int arr[], int left[], int right[], int L, int R){
return (right[L] >= left[R]);
}
int main(){
int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
int N = sizeof(arr) / sizeof(int);
int left[N], right[N];
processArray(arr, N, left, right);
int L = 0;
int R = 2;
if (isMountainSubArray(arr, left, right, L, R))
cout<<"The subarray is in mountain form";
else
cout<<"The subarray is not in mountain form";
return 0;
}
출력
The subarray is in mountain form
위 코드에서 구간 [0, 2]에 해당하는 부분 배열은 {2, 3, 2}로, 값이 증가한 후 감소하므로 산 형태임을 확인할 수 있습니다.