C++로 정렬된 배열에서 더 작은 요소 개수 세기

개요

이 튜토리얼에서는 C++를 사용하여 정렬된 배열에서 주어진 숫자보다 작은 요소의 개수를 세는 방법을 알아봅니다.

정렬된 배열과 하나의 기준 숫자가 주어졌을 때, 배열 내에서 해당 숫자보다 작은 값을 가지는 모든 요소의 개수를 구하는 것이 목표입니다.

upper_bound를 활용한 풀이

배열이 이미 정렬되어 있기 때문에 C++ STL의 upper_bound() 함수를 사용하면 매우 간단하게 해결할 수 있습니다. upper_bound()는 정렬된 범위에서 주어진 값보다 큰 첫 번째 요소의 위치(반복자)를 반환합니다. 따라서 이 위치에서 배열의 시작 주소를 빼면 주어진 값보다 작거나 같은 요소의 개수를 바로 구할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int countSmaller(int arr[], int n, int x){
    return upper_bound(arr, arr + n, x) - arr;
}

int main(){
    int arr[] = { 10, 20, 30, 40, 50 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << countSmaller(arr, n, 45) << endl;
    cout << countSmaller(arr, n, 55) << endl;
    cout << countSmaller(arr, n, 4) << endl;
    return 0;
}

실행 결과

4
5
0

코드 설명

위 코드의 동작을 하나씩 살펴보면 다음과 같습니다.

• countSmaller(arr, n, 45): 45보다 작은 요소는 10, 20, 30, 40으로 총 4개입니다.
• countSmaller(arr, n, 55): 55는 배열의 모든 요소(10~50)보다 크므로 5개입니다.
• countSmaller(arr, n, 4): 4는 배열의 최솟값인 10보다도 작으므로 0개입니다.

시간 복잡도

upper_bound()는 내부적으로 이진 탐색(binary search)을 사용하므로 시간 복잡도는 O(log n)입니다. 배열이 정렬되어 있다는 전제가 주어진다면, 모든 요소를 일일이 순회하는 O(n) 방식보다 훨씬 효율적으로 문제를 해결할 수 있습니다.