C++로 점수 표에서 학생의 순위 구하기: 단계별 풀이와 예제 코드

크기가 n × 4인 2차원 배열이 있다고 가정해 보겠습니다. 학생은 총 n명이며, 각 학생에게는 0부터 n-1까지의 고유 ID가 부여되어 있습니다. 또한 모든 학생은 영어, 지리, 수학, 역사 네 과목의 점수를 가지고 있습니다.

성적표에서 학생들은 네 과목 점수의 합계를 기준으로 내림차순 정렬되며, 합계가 같은 학생이 둘 이상일 경우에는 ID 오름차순으로 정렬됩니다. 우리가 구해야 하는 값은 바로 ID가 0인 학생의 최종 순위입니다.

예를 들어 입력이 아래와 같다고 해봅시다.

이때 출력 결과는 2입니다. ID가 0인 학생의 점수 합계는 398점이고, 이보다 합계가 높은 학생은 400점인 한 명뿐이므로 해당 학생의 순위는 2위가 됩니다.

문제 해결 단계

이 문제는 다음 단계를 따라 해결할 수 있습니다.

1. n을 성적표(2차원 배열)의 크기로 설정합니다.
2. 순위를 나타내는 변수 r을 1로 초기화합니다.
3. 변수 p에 첫 번째 행, 즉 ID가 0인 학생의 네 과목 점수 합계를 저장합니다.
4. i를 1부터 n-1까지 반복하면서, i번째 학생의 점수 합계가 p보다 클 때마다 r을 1씩 증가시킵니다.
5. 모든 반복이 끝난 후 r을 반환합니다. 이 값이 곧 ID 0 학생의 순위입니다.

동점자는 ID 오름차순으로 처리되기 때문에, 합계가 같은 학생들은 세지 않고 합계가 엄격하게 더 높은 경우만 카운트하면 정확한 순위를 얻을 수 있습니다.

n := size of table
r := 1
p := table[0, 0] + table[0, 1] + table[0, 2] + table[0, 3]
for initialize i := 1, when i < n, update (increase i by 1), do:
    if table[i, 0] + table[i, 1] + table[i, 2] + table[i, 3] > p, then:
        (increase r by 1)
return r

예제 코드

아래 C++ 구현 예제를 통해 더 자세히 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> table){
    int n = table.size();
    int r = 1;
    int p = table[0][0] + table[0][1] + table[0][2] + table[0][3];
    for (int i = 1; i < n; i++){
        if (table[i][0] + table[i][1] + table[i][2] + table[i][3] > p)
            r++;
    }
    return r;
}
int main(){
    vector<vector<int>> table = { { 100, 98, 100, 100 }, { 100, 100, 100, 100 }, { 90, 99, 90, 100 }, { 100, 98, 60, 99 } };
    cout << solve(table) << endl;
}

입력

{ { 100, 98, 100, 100 }, { 100, 100, 100, 100 }, { 90, 99, 90, 100 }, { 100, 98, 60, 99 } }

출력

2

복잡도 분석

이 알고리즘은 각 학생의 점수 합계를 한 번씩만 확인하면 되므로 시간 복잡도는 O(n)이며, 추가 메모리 없이 상수 공간(O(1))으로 동작합니다. 학생 수가 많아져도 매우 효율적으로 순위를 계산할 수 있다는 장점이 있습니다.