C++로 배열의 모든 요소 순위(Rank) 구하기: 브루트 포스부터 효율적인 알고리즘까지

이 문제에서는 배열에 있는 모든 요소의 순위를 매겨야 합니다. 가장 작은 수는 가장 낮은 순위를, 가장 큰 수는 가장 높은 순위를 갖습니다. 또한 동일한 값이 여러 번 등장하는 경우, 빈도(중복 횟수)에 따라 순위를 조정해 주어야 합니다. 다음 예시를 살펴보겠습니다.

입력 : 20 30 10
출력 : 2.0 3.0 1.0

입력 : 10 12 15 12 10 25 12
출력 : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0

여기서 10의 순위가 1.5인 이유는 배열에 10이 두 개 존재하기 때문입니다. 만약 이 두 개의 10이 서로 다른 순위, 즉 1과 2를 차지한다고 가정하면, 이 순위들을 두 요소가 균등하게 나눠 갖게 되므로 각각의 순위는 (1+2)/2 = 1.5가 됩니다.

입력 : 1, 2, 5, 2, 1, 60, 3
출력 : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0

문제 해결 접근 방식

이 문제를 해결하는 방법에는 크게 두 가지가 있습니다.

방법 1: 브루트 포스(Brute Force) 접근법

이 방법에서는 배열을 반복문으로 순회하면서 특정 요소 하나를 선택하고, 해당 요소의 순위를 직접 계산합니다. 자기보다 작은 요소의 개수와 같은 값의 개수를 세어 공식을 적용하는 방식입니다.

예제 코드

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

int main() {
    int arr[] = {1, 2, 5, 2, 1, 25, 2}; // 입력 배열
    int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기

    float rank[n] = {0}; // 순위를 저장할 배열
    for (int i = 0; i < n; i++) {
        int r = 1; // arr[i]보다 큰 요소의 개수 + 1
        int s = 1; // arr[i]와 같은 요소의 개수

        for (int j = 0; j < n; j++) {
            if (j != i && arr[j] < arr[i])
                r += 1;

            if (j != i && arr[j] == arr[i])
                s += 1;
        }
        rank[i] = r + (float)(s - 1) / (float) 2; // 공식을 사용하여 순위 계산
    }

    for (int i = 0; i < n; i++) // 순위 출력
        cout << rank[i] << ' ';

    return 0;
}

출력 결과

1.5 4 6 4 1.5 7 4

이 프로그램의 시간 복잡도는 O(N²)입니다. 여기서 N은 배열의 크기입니다. 보시다시피 시간 복잡도가 좋지 않기 때문에, 더 큰 입력 제약 조건에서도 원활하게 동작하도록 효율성을 개선할 필요가 있습니다.

방법 2: 효율적인 접근법 (정렬 활용)

이 방법에서는 새로운 배열을 만들어 정렬합니다. 배열이 정렬되면 동일한 값을 가진 요소들이 서로 인접하게 모이므로, 순서대로 순위를 부여한 후 각 요소의 최종 순위를 계산할 수 있습니다. 중복된 값들은 해당 구간의 순위 합을 빈도수로 나누어 평균 순위를 부여받게 됩니다.

예제 코드

#include <bits/stdc++.h>

using namespace std;

int main() {
    int arr[] = {1, 2, 5, 2, 1, 60, 3}; // 입력 배열
    int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
    float rank[n] = {0}; // 순위를 저장할 배열
    int old[n];
    for(int i = 0; i < n; i++)
    old[i] = arr[i];
    sort(arr, arr+n); // 배열 정렬
    int prev = arr[0];
    int r = 1; // 순위
    int s = 0; // 빈도수
    int tot = 0; // 한 요소가 가질 수 있는 순위의 누적 합
    map<int, float> rrank;

    for (int i = 0; i < n; i++) {
        if(prev == arr[i]) {
            s++;       // 빈도수 증가
            tot += r;  // 순위 누적
        } else {
            float now = 0;
            now = (float)tot/s; // 순위를 균등하게 분배
            rrank[prev] = now;
            prev = arr[i];
            tot = r;
            s = 1;
        }
        r++;
    }
    rrank[arr[n-1]] = (float)tot/s;
    for (int i = 0; i < n; i++) // 순위 출력
        cout << rrank[old[i]] << " ";

    return 0;
}

출력 결과

1.5 3.5 6 3.5 1.5 7 5

코드 설명

이 방법에서는 먼저 배열을 정렬한 후, 시작 지점부터 각 요소에 순위(1부터 시작)를 부여합니다. 이전 요소(prev)와 현재 요소가 같으면 빈도수(s)를 증가시키고 순위의 합(tot)을 누적합니다. 현재 요소가 달라지는 시점에는 지금까지 누적된 순위를 이전 요소들에게 균등하게 나누어 저장하고, 빈도수와 누적합을 초기화한 뒤 코드를 계속 진행합니다. 마지막으로 원본 배열(old)을 기준으로 map에서 순위를 조회하여 결과를 출력함으로써 원래 위치의 순위를 얻을 수 있습니다.

이 방식의 시간 복잡도는 정렬에 의해 지배되므로 O(N log N)으로, 브루트 포스 방식의 O(N²)보다 훨씬 효율적입니다.

마무리

이번 글에서는 배열의 모든 요소의 순위를 찾는 문제를 해결해 보았습니다. 브루트 포스 방식과 정렬을 활용한 효율적인 방식, 두 가지 접근법과 함께 이를 구현한 C++ 프로그램도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 충분히 작성할 수 있으니, 직접 다른 언어로 옮겨 보면서 알고리즘에 대한 이해를 깊게 해보시길 바랍니다.