[C++] 프로그래머스 코딩테스트 입문_등수 매기기

최종코드:

#include <string>
#include <vector>

using namespace std;

struct element {
    int sum;
    int index;
};

// 원하는 comp를 통해 정렬
template <typename T, typename Compare>
void Qsort(vector<T>& arr, int start, int end, Compare comp) {
    if (start >= end) return;
    
    T pivot = arr[(start+end)/2];
    
    int l = start, r = end;
    while (l <= r) {
        while (l <= end && comp(arr[l], pivot)) l++;
        while (r >= start && comp(pivot, arr[r])) r--;

        if (l <= r) {
            swap(arr[l], arr[r]);
            l++; r--;
        }
    }

    if (start < r) Qsort(arr, start, r, comp);
    if (l < end) Qsort(arr, l, end, comp);
}

// 자연수 원소만 가지는 내림차순 벡터의 순위 매기는 함수
vector<int> ranker(const vector<element>& arr) {
    if (arr.empty()) return {};
    
    vector<int> ranks;
    ranks.reserve(arr.size());
    
    int current_rank = 1;
    for (int i = 0; i < arr.size(); ++i) {
        // 이전 원소와 값이 다를 때만 현재 인덱스 기반으로 순위 갱신
        if (i > 0 && arr[i].sum != arr[i - 1].sum) {
            current_rank = i + 1;
        }
        ranks.emplace_back(current_rank);
    }
    return ranks;
}

vector<int> solution(vector<vector<int>> score) {
    vector<int> answer(score.size());
    
    vector<element> rankedElements;
    for (int i=0; i<score.size(); i++) {
        rankedElements.emplace_back( element{score[i][0]+score[i][1], i+1} );
    }
    
    // 성적의 합 기준 내림차순 정렬
    Qsort(rankedElements, 0, rankedElements.size()-1, [](const element& a, const element& b) {
        return a.sum > b.sum;
    });
    
    vector<int> computedRanks = ranker(rankedElements);
    
    for (int i=0; i<rankedElements.size(); i++) {
        answer[rankedElements[i].index-1] = computedRanks[i];
    }
    
    return answer;
}

---

element형 벡터를 element.sum을 기준으로 정렬하는 퀵정렬을 구현했다.

 

평균을 비교하려면 실수형을 고려해야 하는데, 어차피 성적 ≤ 100이므로 합해도 int형 범위이기 때문에

합을 기준으로 비교했다.

 

정렬된 배열 [200, 190, 190, 150, 150, 70, 40]의 순위 [1, 2, 2, 4, 4, 6, 7]를 매겨주는 함수 ranker를 통해 답을 구했다.