C++에서 X보다 작거나 같은 요소가 있는 하위 배열 수 계산

<시간/>

정수와 변수 X를 포함하는 배열 arr[]이 제공됩니다. 목표는 각 하위 배열이 X보다 작거나 같은 요소만 포함하도록 arr[]의 모든 하위 배열을 계산하는 것입니다. 예를 들어 배열이 [1, 2,3] 및 X=2인 경우 하위 배열은 [1], [2] 및 [1,2]

가 됩니다.

예를 들어 이해합시다.

입력 - arr[] ={ 4,3,2,1,6 }; X=3

출력 − X보다 작거나 같은 요소가 있는 하위 배열의 개수는 − 6입니다.

설명 − Subaarays는 −

[3], [2], [1], [3,2], [2,1], [3,2,1]

입력 - arr[] ={ 3,6,2,7,1,8,5 }; X=5

출력 − X보다 작거나 같은 요소가 있는 하위 배열의 개수는 − 4입니다.

설명 − Subaarays는 −

[3], [2], [1], [5]

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

원래 배열과 같은 크기의 이진 배열 temp_arr[]을 만들고 있습니다. 이 이진 배열은 해당 arr[i]가 X보다 작거나 같으면 1을 갖고 그렇지 않으면 0을 갖습니다. 이제 temp_arr[]을 탐색하고 연속 1( arr[]에서 X보다 작은 요소)을 확인합니다. 이러한 각 하위 배열의 길이를 temp에 저장합니다. 길이 temp 배열의 경우. 총 하위 배열은 temp*(temp+1)/2입니다. 이것을 총 개수에 추가하고 temp_arr[]이 끝날 때까지 계속합니다.

배열 arr[] 및 변수 X를 사용합니다.
함수 sub_X(int arr[], int size, int x)는 배열과 x를 가져와서 x보다 작거나 같은 요소만 포함하는 하위 배열의 개수를 반환합니다.
임시 변수 temp와 이러한 하위 배열의 최종 합계를 count로 사용합니다.
arr[]과 같은 길이의 이진 배열 temp_arr[]을 가져옵니다.
for 루프를 사용하여 i=0에서 i까지 배열을 순회합니다.
각 요소 arr[i]<=x에 대해 temp_arr[i]=1 else 0을 설정합니다.
for 루프를 사용하여 temp_arr[]을 탐색합니다.
요소가 temp_arr[i] ==1이면 현재 인덱스 i에서 temp_arr[temp_2]( temp_2=i+1; temp_2
모두 1인 하위 배열의 수는 temp=temp_2-i가 됩니다.
이 하위 배열은 모두 1을 가지며 이는 arr[i]의 모든 요소가 <=x임을 의미합니다. 총 하위 어레이는 temp_3=temp*(temp+1)/2입니다.
두 탐색이 모두 끝나면 개수는 x보다 작거나 같은 숫자를 가진 arr 내의 모든 하위 배열의 총 개수를 갖습니다.

예시

#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