코딩 대회 이후 학생별 최종 순위를 구하는 C++ 코드

문제 개요

크기가 n인 배열 A가 있다고 가정해 봅시다. 어떤 코딩 대회에 총 n명의 학생이 참가하며, 대회 시작 전 각 학생은 양의 정수 형태의 평점(레이팅)을 하나씩 가지고 있습니다. 여기서 A[i]는 i번째 학생의 평점을 의미합니다.

대회가 종료되면 모든 학생은 양의 정수로 표현되는 최종 순위를 하나씩 부여받습니다. 우리는 학생들이 자신의 평점에 맞게 순위를 차지할 것이라고 기대합니다. 즉, 학생 A의 평점이 학생 B보다 엄격하게 낮다면, A는 반드시 B보다 엄격하게 뒤처진(더 큰 번호의) 순위를 받아야 합니다. 이 문제의 목표는 대회 종료 시점의 각 학생의 최종 순위를 구하는 것입니다.

예를 들어 입력이 A = [3, 5, 3, 4, 5]라고 한다면 출력은 [4, 1, 4, 3, 1]이 됩니다. 그 이유는 다음과 같습니다. 2번째와 5번째 학생이 가장 높은 평점 5점을 기록하여 공동 1위를 차지하고, 4번째 학생은 4점으로 두 명보다 낮으므로 3위가 되며, 1번째와 3번째 학생은 3점으로 공동 4위를 기록하기 때문입니다. 동점자는 같은 순위를 공유하고, 그 다음 순위는 앞선 인원 수만큼 건너뛰는 방식입니다.

풀이 접근 방법

이 문제는 각 학생마다 '자신보다 평점이 높은 학생의 수'를 세어 해결할 수 있습니다. 특정 학생보다 평점이 높은 사람이 k명이라면, 해당 학생의 순위는 k + 1이 됩니다. 알고리즘의 흐름은 다음과 같습니다.

n := 배열 A의 크기
i := 0부터 시작하여 i < n을 만족하는 동안 i를 1씩 증가시키며 반복:
    d := 1
    j := 0부터 시작하여 j < n을 만족하는 동안 j를 1씩 증가시키며 반복:
        만약 A[j] > A[i]라면:
            d를 1만큼 증가
    d와 ", "를 출력

즉, 바깥쪽 반복문으로 각 학생을 하나씩 선택하고, 안쪽 반복문에서 전체 학생과 평점을 비교하여 더 높은 평점의 개수를 셉니다. 초기값 1에 그 개수를 더한 값이 곧 해당 학생의 최종 순위입니다.

구현 예제

아래의 C++ 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A){
    int n = A.size();
    for (int i = 0; i < n; i++){
        int d = 1;
        for (int j = 0; j < n; j++){
            if (A[j] > A[i])
                d++;
        }
        cout << d << ", ";
    }
}
int main(){
    vector<int> A = { 3, 5, 3, 4, 5 };
    solve(A);
}

입력

{ 3, 5, 3, 4, 5 }

출력

4, 1, 4, 3, 1,

복잡도 분석

이 방법은 모든 학생 쌍을 서로 비교하는 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 학생 수가 많아지면 비효율적일 수 있으며, 이 경우 배열을 정렬하거나 평점별 등장 횟수를 세는 방식을 활용하면 O(n log n) 또는 O(n + max(A)) 수준으로 최적화할 수 있습니다. 하지만 문제의 요구사항을 직관적으로 구현한 기본 풀이로는 위 코드가 적합합니다.