C++로 정렬된 배열에서 k보다 큰 요소 개수 구하기

이 문제에서는 N개의 정렬된 정수 값으로 이루어진 배열 arr[]와 하나의 정수 k가 주어집니다. 우리의 목표는 정렬된 배열에서 k보다 큰 요소의 개수를 찾는 것입니다.

문제 이해하기

예제를 통해 문제를 자세히 살펴보겠습니다.

입력

arr[] = {1, 2, 5, 7, 8, 9}, k = 4

출력

4

설명

k = 4보다 큰 요소는 다음과 같습니다.
5, 7, 8, 9

해결 방법 1: 선형 탐색

가장 단순한 해결 방법은 배열을 처음부터 끝까지(0부터 N까지) 순회하는 것입니다. 순회 중에 k보다 큰 첫 번째 요소를 만나면 해당 위치를 기준으로 남은 요소의 개수를 세면 됩니다. 배열이 정렬되어 있으므로, 첫 번째로 큰 요소를 찾은 시점 이후의 모든 값은 반드시 k보다 큽니다.

예제 코드

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int findGreaterCount(int arr[], int n, int k){
    for(int i = 0; i < n; i++){
        if(arr[i] > k)
            return (n - i);
    }
    return -1;
}

int main(){
    int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
    return 0;
}

출력

The number of elements greater than k is 5

위 코드는 올바르게 동작하지만, 최악의 경우 배열 전체를 순회해야 하므로 시간 복잡도가 O(N)입니다. 배열의 크기가 커질수록 성능 저하가 발생할 수 있습니다.

해결 방법 2: 이진 탐색 활용

배열이 이미 정렬되어 있다는 점을 활용하면 더 효율적인 접근이 가능합니다. 이진 탐색(Binary Search)을 사용하여 k보다 큰 첫 번째 요소의 인덱스를 찾으면, 전체 개수에서 해당 인덱스를 뺀 값이 곧 k보다 큰 요소의 개수가 됩니다.

이진 탐색은 매번 탐색 범위를 절반으로 줄여 나가기 때문에, 시간 복잡도를 O(log N)으로 크게 줄일 수 있습니다.

예제 코드

아래 프로그램은 이진 탐색 기반 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int findGreaterCount(int arr[], int n, int k){
    int s = 0;
    int e = n - 1;
    int firstGreaterEle = n;

    while (s <= e) {
        int mid = s + (e - s) / 2;
        if (arr[mid] > k) {
            firstGreaterEle = mid;
            e = mid - 1;
        }
        else
            s = mid + 1;
    }
    return (n - firstGreaterEle);
}

int main(){
    int arr[] = { 1, 3, 5, 7, 7, 8, 12, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout<<"The number of elements greater than k is "<<findGreaterCount(arr, n, k);
    return 0;
}

출력

The number of elements greater than k is 5

마무리

배열이 정렬되어 있다면 이진 탐색을 활용하는 것이 선형 탐색보다 훨씬 효율적입니다. 선형 탐색은 O(N)의 시간 복잡도를 가지는 반면, 이진 탐색은 O(log N)으로 대규모 데이터에서도 빠른 성능을 보장합니다. 또한, C++ 표준 라이브러리의 std::upper_bound 함수를 사용하면 동일한 로직을 더 간결하게 구현할 수 있습니다.