카카오 2018 블라인드 테스트: 실패율 C++

https://www.welcomekakao.com/learn/courses/30/lessons/42889

stage k의 실패율은, 현재 stage k에 머물러 있는 사람/스테이지 k이상 시도한 사람

이라는 것을 이용했다. 두 배열을 만든 이후에, 부동 소수점 오차를 방지하기 위해서 나누는 연산은 하지 않고, 통분시 분자값을 비교해서 대소를 비교했다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll cnt[502], d[502];
 
struct Info {
    ll idx, son = 0, mom = 0;
}info[502];
 
bool cmp(Info a, Info b) {
 
    if (a.son * b.mom > b.son * a.mom) return true;
    else if (a.son * b.mom == b.son * a.mom) {
        return a.idx < b.idx;
    }
    else
        return false;
}
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    for (int i = 0; i < stages.size(); i++) {
        cnt[stages[i]]++;
        for (int j = 1; j <= stages[i]; j++) {
            d[j]++;
        }
    }
    for (int i = 1; i <= N; i++) {
        info[i].idx = i;
        info[i].son = cnt[i];
        info[i].mom = d[i];
    }
    sort(info + 1, info + N+1, cmp);
 
    for (int i = 1; i <= N; i++)
        answer.push_back(info[i].idx);
    return answer;
}