정수로 이루어진 배열 arr[]와 변수 X가 주어졌을 때, 모든 요소가 X보다 작거나 같은 부분 배열(subarray)의 개수를 구하는 것이 목표입니다. 예를 들어 배열이 [1, 2, 3]이고 X = 2라면, 조건을 만족하는 부분 배열은 [1], [2], [1, 2]로 총 3개입니다.
예제 입력 및 출력
입력 − arr[] = { 4, 3, 2, 1, 6 }, X = 3
출력 − X 이하의 요소만 포함하는 부분 배열의 개수는 6개입니다.
설명 − 조건을 만족하는 부분 배열은 다음과 같습니다.
[3], [2], [1], [3,2], [2,1], [3,2,1]
입력 − arr[] = { 3, 6, 2, 7, 1, 8, 5 }, X = 5
출력 − X 이하의 요소만 포함하는 부분 배열의 개수는 4개입니다.
설명 − 조건을 만족하는 부분 배열은 다음과 같습니다.
[3], [2], [1], [5]
문제 해결 접근 방식
원본 배열 arr[]와 크기가 같은 이진(binary) 배열 temp_arr[]를 하나 만듭니다. arr[i]가 X보다 작거나 같으면 temp_arr[i]에 1을, 그렇지 않으면 0을 저장합니다. 이렇게 하면 "X 이하의 요소가 연속으로 이어지는 구간"이 temp_arr[]에서 "연속된 1의 구간"으로 표현됩니다.
길이가 n인 연속된 1의 구간 하나에서 만들 수 있는 부분 배열의 개수는 n × (n + 1) / 2입니다. 길이 1짜리가 n개, 길이 2짜리가 n−1개, …, 길이 n짜리가 1개씩 만들어지기 때문입니다. 따라서 temp_arr[]를 순회하면서 연속된 1의 구간 길이를 temp에 기록하고, temp × (temp + 1) / 2를 결과에 누적하면 전체 개수를 구할 수 있습니다.
알고리즘 단계
- 배열 arr[]와 변수 X를 입력받습니다.
- sub_X(int arr[], int size, int x) 함수는 배열과 x를 받아, x 이하의 요소만으로 이루어진 부분 배열의 개수를 반환합니다.
- 연속 구간의 길이를 저장할 임시 변수 temp와 최종 결과를 저장할 count를 준비합니다.
- arr[]와 길이가 같은 이진 배열 temp_arr[]를 생성합니다.
- for 루프로 i = 0부터 i < size까지 arr[]를 순회하면서, arr[i] ≤ x이면 temp_arr[i] = 1, 아니면 0으로 설정합니다.
- for 루프로 temp_arr[]를 순회합니다.
- temp_arr[i] == 1인 지점을 만나면, 내부 루프로 temp_2 = i + 1부터 temp_2 < size 동안 temp_arr[temp_2]가 1인 동안 진행하고, 0을 만나면 내부 루프를 종료합니다.
- 연속된 1 구간의 길이는 temp = temp_2 − i가 됩니다.
- 해당 구간의 모든 값이 1이라는 것은 arr[]의 그 구간 요소들이 모두 x 이하라는 의미이므로, 만들 수 있는 부분 배열의 수는 temp_3 = temp × (temp + 1) / 2입니다.
- 모든 순회가 끝나면 count에는 arr[] 내에서 x 이하의 숫자만 포함하는 모든 부분 배열의 총 개수가 저장됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int sub_X(int arr[], int size, int x){
int count = 0, temp = 0;
int temp_arr[size];
for (int i = 0; i < size; i++){
if (arr[i] <= x){
temp_arr[i] = 1;
}
else{
temp_arr[i] = 0;
}
}
for (int i = 0; i < size; i++){
if (temp_arr[i] == 1){
int temp_2;
for(temp_2 = i + 1; temp_2 < size; temp_2++){
if(temp_arr[temp_2] != 1){
break;
}
}
temp = temp_2 - i;
int temp_3 = (temp) * (temp + 1)/2;
count = count + temp_3;
i = temp_2;
}
}
return count;
}
int main(){
int arr[] = { 2, 6, 1, 10, 5, 3 };
int x = 4;
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of sub-arrays which have elements less than or equal to X are: "<<sub_X(arr, size, x);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of sub-arrays which have elements less than or equal to X are: 3
복잡도 분석
위 구현은 중첩 루프를 사용하므로 최악의 경우 시간 복잡도는 O(n²)이며, 보조 배열 temp_arr[]로 인해 공간 복잡도는 O(n)입니다.
참고로 이 문제는 한 번의 순회만으로도 해결할 수 있습니다. arr[i] ≤ x이면 현재 연속 구간의 길이를 1 증가시키고, 아니면 0으로 초기화한 뒤 매 단계마다 누적 개수에 현재 길이를 더하면 됩니다. 이렇게 하면 길이 L인 구간의 부분 배열 수 L × (L + 1) / 2가 자동으로 합산되어 전체 시간 복잡도를 O(n)까지 줄일 수 있습니다.