C++로 배열의 각 요소별 서퍼서(Surpasser) 개수 구하기

문제 개요

배열 A가 하나 주어졌을 때, 각 요소의 서퍼서(surpasser) 개수를 구하는 것이 목표입니다. 서퍼서란 현재 요소보다 오른쪽에 위치하면서 값이 더 큰 원소들을 의미합니다.

예를 들어 A = {2, 7, 5, 3, 0, 8, 1}이라면 각 요소의 서퍼서 개수는 {4, 1, 1, 1, 2, 0, 0}이 됩니다. 첫 번째 요소인 2의 오른쪽에는 7, 5, 3, 8처럼 2보다 큰 숫자가 네 개 있으므로 서퍼서는 4개이며, 나머지 요소들도 같은 방식으로 계산됩니다.

접근 방법

풀이 방법은 매우 간단합니다. 두 개의 중첩 반복문을 사용합니다. 바깥 반복문으로 각 요소를 선택하고, 안쪽 반복문에서 해당 요소 오른쪽에 있는 값들 중 더 큰 값의 개수를 센 뒤, 그 결과를 별도의 배열에 저장하면 됩니다.

알고리즘 단계

1. 결과를 저장할 배열 surpassers[]를 준비합니다.
2. 각 인덱스 i에 대해, i+1부터 배열 끝까지 값을 검사합니다.
3. arr[j] > arr[i]를 만족하면 카운트를 증가시킵니다.
4. 카운트 값을 surpassers[i]에 저장합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

void getSurpassers(int arr[], int surpassers[], int n){
    for(int i = 0; i < n; i++){
        int count = 0;
        for(int j = i + 1; j < n; j++){
            if(arr[j] > arr[i])
                count++;
        }
        surpassers[i] = count;
    }
}

void displayArray(int arr[], int n){
    for(int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main() {
    int arr[] = {2, 7, 5, 3, 0, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int surpassers[n];
    cout << "Elements : "; displayArray(arr, n);
    getSurpassers(arr, surpassers, n);
    cout << "Surpassers : "; displayArray(surpassers, n);
}

실행 결과

Elements : 2 7 5 3 0 8 1
Surpassers : 4 1 1 1 2 0 0

복잡도 분석

• 시간 복잡도: O(n²) — 모든 요소 쌍을 비교해야 하므로 이중 반복문이 필요합니다.
• 공간 복잡도: O(n) — 결과를 저장할 추가 배열이 하나 필요합니다.

배열의 크기가 클 경우 O(n log n) 시간에 해결할 수 있는 병합 정렬 기반 접근이나 이진 인덱스 트리(BIT) 방식도 고려할 수 있습니다.