[정렬 알고리즘] 실패율 ★☆☆

기출 : 2019 카카오 신입 공채 1차

 

STL sort함수를 이용한 간단한 문제였다

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int,double> a, pair<int,double> b){
    if(a.second>b.second) return true;
    else if(a.second<b.second) return false;
    else return a.first<b.first;
}

vector<int> solution(int N, vector<int> stages) {
    vector<pair<int,double>> v;
    int left=stages.size();
    sort(stages.begin(), stages.end());
    for(int i=1;i<=N;i++){
        double cnt=0;
        for(int j=0;j<stages.size();j++){
            if(stages[j]==i) cnt+=1;
            else if(stages[j]>i) break;
        }
        v.push_back({i,cnt/left});
        left-=cnt;
    }
    sort(v.begin(),v.end(),cmp);
    vector<int> answer;
    for(int i=0;i<N;i++) answer.push_back(v[i].first);
    return answer;
}