C++ STL Set을 활용해 오른쪽에 있는 더 작은 요소 개수 구하기

이 튜토리얼에서는 C++ STL의 set 컨테이너를 활용하여 배열에서 각 요소의 오른쪽에 위치한 더 작은 요소의 개수를 계산하는 방법을 알아봅니다.

하나의 정수 배열이 주어졌을 때, 새로운 배열을 생성하고 각 위치에 '현재 요소보다 오른쪽에 있으면서 값이 작은 요소'의 개수를 저장하는 것이 목표입니다.

알고리즘 동작 원리

핵심 아이디어는 배열을 오른쪽에서 왼쪽으로 순회하면서 지금까지 확인한 요소들을 set에 삽입하는 것입니다. set은 자동으로 정렬된 상태를 유지하기 때문에, lower_bound() 함수로 현재 요소의 위치를 찾으면 그 앞에 있는 요소의 개수가 곧 더 작은 요소의 개수가 됩니다.

1. 배열의 마지막 요소부터 첫 번째 요소까지 역순으로 순회합니다.
2. 현재 요소를 set에 삽입합니다.
3. lower_bound(A[i])로 현재 요소와 같거나 큰 첫 번째 위치를 찾습니다.
4. set의 시작부터 해당 위치까지의 거리(distance)가 바로 오른쪽에 있는 더 작은 요소의 개수입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
void count_Rsmall(int A[], int len){
   set<int> s;
   int countSmaller[len];
   for (int i = len - 1; i >= 0; i--) {
      s.insert(A[i]);
      auto it = s.lower_bound(A[i]);
      countSmaller[i] = distance(s.begin(), it);
   }
   for (int i = 0; i < len; i++)
      cout << countSmaller[i] << " ";
}
int main(){
   int A[] = {12, 1, 2, 3, 0, 11, 4};
   int len = sizeof(A) / sizeof(int);
   count_Rsmall(A, len);
   return 0;
}

출력 결과

6 1 1 1 0 1 0

시간 복잡도 분석

C++의 set은 내부적으로 균형 이진 탐색 트리(레드-블랙 트리)로 구현되어 있어, 삽입과 lower_bound 연산 각각 O(log n)의 시간이 소요됩니다. 따라서 전체 시간 복잡도는 O(n log n)으로, 모든 쌍을 비교하는 O(n²) 브루트 포스 방식보다 훨씬 효율적입니다. 특히 배열의 크기가 클 때 이 접근 방식의 장점이 두드러집니다.