C++에서 비증가(내림차순) 순서로 정렬된 벡터의 lower_bound()와 upper

이 글에서는 C++ STL에서 비증가(non-increasing) 순서, 즉 내림차순으로 정렬된 배열에 대해 vector::lower_bound()와 vector::upper_bound()를 사용하는 방법을 자세히 살펴봅니다.

벡터(vector)는 동적 배열과 유사한 컨테이너입니다. 요소를 삽입하거나 삭제할 때마다 내부 저장 공간의 크기가 자동으로 조절되므로, 개발자가 직접 메모리 크기를 관리할 필요가 없다는 장점이 있습니다.

lower_bound()와 upper_bound()란?

일반적으로 오름차순으로 정렬된 범위에서는 lower_bound가 주어진 값보다 작지 않은(크거나 같은) 첫 번째 요소를 가리키는 반복자를 반환하고, upper_bound는 주어진 값보다 큰 첫 번째 요소를 가리키는 반복자를 반환합니다.

그러나 벡터가 내림차순으로 정렬되어 있다면 비교 방향이 반대이므로, greater<int>()와 같은 비교 함수를 함께 전달해야 올바른 결과를 얻을 수 있습니다. 내림차순 기준으로는 다음과 같이 동작합니다.

lower_bound: 주어진 값보다 크지 않은(작거나 같은) 첫 번째 요소를 가리키는 반복자를 반환합니다.
upper_bound: 주어진 값보다 작은 첫 번째 요소를 가리키는 반복자를 반환합니다.

예시 1

입력

30 30 30 20 20 20 10 10

출력

Lower bound of 20 = 3
Upper bound of 20 = 6

예시 2

입력

9 9 8 8 8 7 7 7 6 6 6 6

출력

Lower bound of 7 = 5
Upper bound of 7 = 8

반환 값

lower_bound는 조건을 만족하는 범위의 첫 번째 요소를 가리키는 반복자를 반환하고, upper_bound는 해당 값 구간 바로 다음 위치, 즉 값보다 작은 첫 번째 요소를 가리키는 반복자를 반환합니다. 따라서 두 반복자의 차이를 계산하면 해당 값이 벡터 안에 몇 번 등장하는지도 손쉽게 알 수 있습니다.

문제 해결 접근 방식

먼저 벡터를 초기화합니다.
벡터의 요소들을 비증가(내림차순) 순서로 정렬합니다.
lower_bound를 구합니다.
upper_bound를 구합니다.
마지막으로 두 경계의 인덱스를 출력합니다.

주의: lower_bound와 upper_bound는 이진 탐색(binary search)을 기반으로 동작하므로, 벡터가 반드시 정렬되어 있어야 합니다. 정렬되지 않은 벡터에서는 올바른 결과를 보장할 수 없습니다. 또한 내림차순으로 정렬했다면 두 함수에도 동일한 비교 함수(greater<int>())를 전달해야 한다는 점을 잊지 마세요. 두 함수의 시간 복잡도는 모두 O(log n)으로 매우 효율적입니다.

예제 1: 내림차순 정렬된 벡터에서 17 찾기

// C++ 프로그램: 내림차순 정렬된 벡터에서 lower_bound와 upper_bound 사용하기
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int vect[] = {13, 13, 13, 16, 16, 16, 17, 17, 17, 17, 18, 18};
    int n = sizeof(vect) / sizeof(vect[0]);
    vector<int> v(vect, vect + n);

    // 내림차순 정렬
    sort(v.begin(), v.end(), greater<int>());

    cout << "\nSorted Vector: ";
    for (auto i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";

    vector<int>::iterator low, up;
    // 내림차순이므로 greater<int>()를 비교 함수로 전달
    low = lower_bound(v.begin(), v.end(), 17, greater<int>());
    up = upper_bound(v.begin(), v.end(), 17, greater<int>());

    cout << "\nLower bound = " << (low - v.begin());
    cout << "\nUpper bound = " << (up - v.begin());

    return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Sorted Vector: 18 18 17 17 17 17 16 16 16 13 13 13
Lower bound = 2
Upper bound = 6

예제 2: 내림차순 정렬된 벡터에서 8 찾기

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int vect[] = {5, 5, 5, 5, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10};
    int n = sizeof(vect) / sizeof(vect[0]);
    vector<int> v(vect, vect + n);

    // 내림차순 정렬
    sort(v.begin(), v.end(), greater<int>());

    cout << "\nSorted Vector: ";
    for (auto i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";

    vector<int>::iterator low, up;
    low = lower_bound(v.begin(), v.end(), 8, greater<int>());
    up = upper_bound(v.begin(), v.end(), 8, greater<int>());

    cout << "\nLower bound = " << (low - v.begin());
    cout << "\nUpper bound = " << (up - v.begin());

    return 0;
}

실행 결과는 다음과 같습니다.

Sorted Vector: 10 10 9 9 9 8 8 8 8 7 7 7 5 5 5 5
Lower bound = 5
Upper bound = 9

정리

내림차순으로 정렬된 벡터에서 lower_bound와 upper_bound를 사용할 때는 반드시 greater<int>()와 같은 비교 함수를 함께 전달해야 합니다. 이를 통해 특정 값이 시작되는 위치와 끝나는 위치를 O(log n) 시간 안에 효율적으로 찾을 수 있으며, 두 반복자의 차이를 이용하면 해당 값의 등장 횟수까지 간단히 구할 수 있습니다.

C++에서 비증가(내림차순) 순서로 정렬된 벡터의 lower_bound()와 upper_bound() 활용법