프로그래머스 입문 120882 등수 매기기

2026. 08. 08

문제

각 학생의 영어와 수학 점수가 담긴 2차원 정수 배열이 주어진다.
각 학생의 평균 점수를 기준으로 등수를 매긴 배열을 반환하시오.

score	result
[[80, 70], [90, 50], [40, 70], [50, 80]]	[1, 2, 4, 3]
[[80, 70], [70, 80], [30, 50], [90, 100], [100, 90], [100, 100], [10, 30]]	[4, 4, 6, 2, 2, 1, 7]

풀이

전수 비교

#include <stdlib.h>

int* solution(int** score, size_t score_rows, size_t score_cols)
{
    int* result = malloc(sizeof(int) * score_rows);
    int* total_scores = calloc(score_rows, sizeof(int));

    for (size_t student = 0; student < score_rows; student++)
    {
        for (size_t subject = 0; subject < score_cols; subject++)
        {
            total_scores[student] += score[student][subject];
        }
    }

    for (size_t student = 0; student < score_rows; student++)
    {
        result[student] = 1;

        for (size_t other_student = 0; other_student < score_rows; other_student++)
        {
            if (total_scores[student] < total_scores[other_student])
            {
                result[student]++;
            }
        }
    }

    free(total_scores);

    return result;
}

모든 학생이 응시한 과목 수가 같으므로, 평균 점수 대신 총점을 비교해도 순위는 동일하다.

첫 번째 이중 반복문에서는 각 학생의 과목별 점수를 모두 더해 총점을 계산한다.
두 번째 이중 반복문에서는 각 학생의 총점을 다른 학생들의 총점과 비교한다.
자신보다 총점이 높은 학생이 있을 때마다 등수를 1씩 증가시키면 최종 순위를 구할 수 있다.

각 학생의 총점을 다른 모든 학생의 총점과 비교하므로 이 풀이의 전체 시간 복잡도는 O(n²)이다.

등수는 0이 아닌 1부터 시작해야 한다.
하지만 memset은 바이트 단위로 값을 채우기 때문에 int 배열의 각 원소를 1로 초기화하는 데 사용할 수 없다.
32비트 int를 기준으로 memset을 사용해 1로 초기화하면 각 바이트가 0x01로 채워져 0x01010101, 즉 16,843,009가 된다.
따라서 두 번째 이중 반복문에서 각 학생의 등수를 1로 초기화한 뒤 비교를 진행한다.

두 번째 이중 반복문에서는 바깥쪽 반복문의 student와 안쪽 반복문의 other_student가 같아지는 경우가 있다.
같은 학생끼리는 비교할 필요가 없으므로 continue를 사용해 건너뛸 수도 있지만, 별도의 처리를 하지 않아도 된다.
자기 자신과 비교하는 경우에는 총점이 같아 비교 조건을 만족하지 않으므로 등수에 아무런 영향을 주지 않기 때문이다.

정렬

#include <stdlib.h>

typedef struct
{
    int sum;
    int index;
} Student;

int compare(const void* a, const void* b)
{
    const Student* left = a;
    const Student* right = b;

    return right->sum - left->sum;
}

int* solution(int** score, size_t score_rows, size_t score_cols)
{
    Student* students = malloc(sizeof(Student) * score_rows);
    int* result = malloc(sizeof(int) * score_rows);

    for (size_t student = 0; student < score_rows; student++)
    {
        students[student].sum = 0;
        students[student].index = student;

        for (size_t subject = 0; subject < score_cols; subject++)
        {
            students[student].sum += score[student][subject];
        }
    }

    qsort(students, score_rows, sizeof(Student), compare);

    for (size_t i = 0; i < score_rows; i++)
    {
        if (i > 0 && students[i].sum == students[i - 1].sum)
        {
            result[students[i].index] = result[students[i - 1].index];
        }
        else
        {
            result[students[i].index] = i + 1;
        }
    }

    free(students);

    return result;
}

구조체 없이 총점만 구해 내림차순으로 정렬하면 총점의 순서는 알 수 있지만, 각 총점이 원래 어느 학생의 것인지는 알 수 없다.
따라서 총점과 원래 학생 번호를 Student 구조체로 묶어 함께 정렬한다.
sum은 등수를 계산할 기준이고, index는 원래 학생의 위치다.

내림차순 정렬이 되어 있더라도, 동점자가 존재하므로 모든 학생에게 단순히 i + 1을 등수로 매길 수 없다.
이 문제에서는 2등이 두 명이라면 그다음 학생은 3등이 아니라 4등이 된다.
따라서 현재 학생의 총점이 앞 학생과 같으면 앞 학생의 등수를 그대로 복사하고, 다르면 i + 1을 현재 학생의 등수로 저장한다.

총점을 계산하고 정렬한 뒤 등수를 매기는데, 정렬이 가장 많은 시간이 걸리므로 이 풀이의 전체 시간 복잡도는 O(n log n)이다.

문제 변형

이 문제에서는 2등이 두 명이면 3등이 없고 다음 학생이 4등이 된다.
하지만 현실에서는 공동 등수 뒤에도 순위를 연속해서 매기는 방식이 더 자연스럽다.
공동 등수 다음에도 순위를 이어서 매기도록 바꾸면 등수는 다음과 같다.

score	기존 result	변형 result
[[80, 70], [70, 80], [30, 50], [90, 100], [100, 90], [100, 100], [10, 30]]	[4, 4, 6, 2, 2, 1, 7]	[3, 3, 4, 2, 2, 1, 5]

이 규칙은 정렬을 이용한 풀이에서 등수를 매기는 반복문만 다음처럼 바꾸면 구현할 수 있다.

int rank = 1;

for (size_t i = 0; i < score_rows; i++)
{
    if (i > 0 && students[i].sum != students[i - 1].sum)
        rank++;

    result[students[i].index] = rank;
}

등수는 1부터 시작하므로 rank의 초깃값을 1로 설정한다.
이후 앞 학생과 총점이 다를 때, 즉 새로운 총점이 나타날 때만 rank를 1씩 증가시킨다.
따라서 동점자는 같은 등수를 받고, 공동 등수 다음의 순위를 건너뛰지 않는다.