[프로그래머스][C++] 등수 매기기

등수 매기기

문제 링크

등수 매기기

분석

score는 2차원 배열로, [영어 점수, 수학점수]를 의미합니다.

각 학생의 평균 점수를 기준으로 등수를 매기고, 등수들을 배열로 반환하는 문제입니다.

평균이 같은 경우 동순위 처리를 합니다.
예를 들어 1등이 2명인 경우 2등이 없이 다음 등수는 3등이 됩니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<vector<int>> score) {
    vector<int> answer;
    
    // 평균 점수를 저장하는 벡터
    vector<float> averages;
    // 평균 점수 계산 및 저장
    for (int i = 0; i < score.size(); ++i)
    {
        // 평균을 구한다.
        float average = (score[i][0] + score[i][1]) / 2.f;

        averages.push_back(average);
    }
    
    // 평균을 내림차순으로 정렬한 벡터
    vector<float> sortAverages = averages;
    sort(sortAverages.begin(), sortAverages.end(), greater<float>());
    
    // 모든 점수를 순회하는 반복문
    for (int i = 0; i < score.size(); ++i)
    {
        // 특정 점수가 몇 번째에 위치하는지 찾습니다.
        auto it = find(sortAverages.begin(), sortAverages.end(), averages[i]);
        // 찾은 위치가 시작 위치에서 얼마나 먼지 찾습니다.
        // 해당 위치의 +1이 등수가 됩니다.
        answer.push_back(distance(sortAverages.begin(), it) + 1);
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n^2)$입니다.

• 평균을 구하고, 저장하는 반복문 $O(n)$
• 정렬 $O(n \ log \ n)$
• 등수 찾기 $O(n \tiems n)$
• $O(n) + O(n \ log \ n) + O(n \tiems n)$

공간 복잡도는 $O(n)$입니다.

• 평균 점수를 저장하는 벡터 vector<float> averages $O(n)$
• 평균을 내림차순으로 정렬한 벡터 vector<float> sortAverages $O(n)$
• 반환 값을 저장하는 벡터 vector<int> answer $O(n)$
• $O(n) + O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.14MB)
테스트 2 〉 통과 (0.01ms, 4.15MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.14MB)
테스트 6 〉 통과 (0.01ms, 4.21MB)
테스트 7 〉 통과 (0.01ms, 3.65MB)
테스트 8 〉 통과 (0.01ms, 4.16MB)
테스트 9 〉 통과 (0.01ms, 4.21MB)
테스트 10 〉 통과 (0.01ms, 4.03MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 4.16MB)