배열과 함께 부분 배열의 시작 인덱스(lower)와 끝 인덱스(upper), 그리고 기준이 되는 숫자가 주어졌을 때, 해당 범위 안에서 기준 숫자보다 작거나 같은 요소가 몇 개 있는지 세는 문제입니다. 예제를 통해 살펴보겠습니다.
입력
arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 4 lower = 0 upper = 5
출력
4
인덱스 0부터 5 사이에는 4보다 작거나 같은 요소가 총 4개(1, 2, 3, 4) 있습니다.
알고리즘
배열, 기준 숫자, 부분 배열의 인덱스를 초기화합니다.
개수를 저장할 변수 count를 0으로 초기화합니다.
부분 배열의 lower 인덱스부터 upper 인덱스까지 반복하는 루프를 작성합니다.
현재 요소가 주어진 숫자보다 작거나 같으면 count를 1 증가시킵니다.
최종 count 값을 반환합니다.
구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n, int lower, int upper, int k) {
if (lower < 0 || upper >= n || lower > upper) {
return 0;
}
int count = 0;
for (int i = lower; i <= upper; i++) {
if (arr[i] <= k) {
count += 1;
}
}
return count;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
int n = 8, k = 4;
cout << getElementsCount(arr, n, 0, 3, k) << endl;
cout << getElementsCount(arr, n, 4, 7, k) << endl;
return 0;
}코드에서 getElementsCount 함수는 먼저 유효성 검사를 수행합니다. lower가 0보다 작거나, upper가 배열 크기 이상이거나, lower가 upper보다 크면 잘못된 범위이므로 0을 반환합니다. 그 후 주어진 범위를 순회하면서 조건에 맞는 요소의 개수를 세어 반환합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
4 0
첫 번째 호출은 인덱스 0부터 3까지의 범위에서 4 이하인 요소를 세어 4를 출력하고, 두 번째 호출은 인덱스 4부터 7까지의 범위에 4 이하인 요소가 없으므로 0을 출력합니다. 이 알고리즘의 시간 복잡도는 O(n)이며, 추가 메모리 사용 없이 O(1) 공간 복잡도로 해결할 수 있습니다.