C++를 사용하여 모든 요소가 X보다 큰 세그먼트 수 찾기

이 기사에서는 주어진 수 X보다 큰 요소가 있는 주어진 시퀀스에서 세그먼트 또는 하위 배열의 수를 찾아야 합니다.

겹치는 세그먼트는 한 번만 계산할 수 있으며 두 개의 연속 요소 또는 세그먼트는 별도로 계산해서는 안 됩니다. 여기 주어진 문제의 기본 예가 있습니다 -

Input : arr[ ] = { 9, 6, 7, 11, 5, 7, 8, 10, 3}, X = 7
Output : 3
Explanation : { 9 }, { 11 } and { 8, 10 } are the segments greater than 7

Input : arr[ ] = { 9, 6, 12, 2, 11, 14, 8, 14 }, X = 8
Output : 4
Explanation : { 9 }, { 12 }, { 11, 14 } and { 14 } are the segments greater than 8

해결책을 찾기 위한 접근 방식

순진한 접근

이 문제에서는 변수 상태를 초기화하고 있습니다. 0으로 지정하고 주어진 배열 처리를 시작하고 X보다 큰 요소가 발견되면 상태를 1로 변경하고 요소를 계속 처리하고 X보다 작거나 같은 숫자가 발견되면 상태를 다시 0으로 변경하고 1로 계수를 증가시킵니다. 상태가 1로 갔다가 다시 0으로 돌아갈 때마다.

예시

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 9, 6, 12, 2, 11, 14, 8, 14 };
    int n = sizeof (a) / sizeof (a[0]);
    int X = 8;
    int state = 0;
    int count = 0;
    // traverse the array
    for (int i = 0; i < n; i++){
        // checking whether element is greater than X
        if (a[i] > X){
           state = 1;
        }
        else{
           // if flag is true
           if (state)
               count += 1;
            state = 0;
        }
    }
    // checking for the last segment
    if (state)
        count += 1;
    cout << "Number of segments where all elements are greater than X: " << count;
    return 0;
}

출력

Number of segments where all elements are greater than X: 4

위 프로그램 설명

위의 프로그램에서 상태를 스위치로 사용하고 있으며 X보다 큰 숫자가 발견되면 1로 설정하고 X보다 작거나 같은 숫자가 발견되면 0으로 설정하고 모든 시간 상태에 대해 1로 갔다가 0으로 돌아오면 카운트를 1씩 증가시킵니다. 마지막으로 카운트에 저장된 결과를 인쇄합니다.

결론

이 글에서는 세그먼트를 찾을 때마다 상태를 1과 0으로 설정하는 접근 방식을 적용하여 모든 요소가 X보다 큰 세그먼트의 수를 찾는 문제를 해결합니다. C, Java, Python 등과 같은 다른 프로그래밍 언어로 이 프로그램을 작성할 수 있습니다.