Level 1. 실패율

Level 1. 실패율

 

 

stages 벡터를 정렬하거나 count_if() 함수를 이용할 수도 있지만 나는 각 스테이지별 도달한 사람 수를 미리 계산하여 사용했다.

 

1 ~ N을 갖는 인덱스 배열을 만들고 실제 정렬은 reached_users 벡터에 인덱스를 전달해 수행할 수 있다.

 

stable_sort() 함수를 사용하면 같은 순위를 갖는 원소의 순서를 유지할 수 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// i+1번째 스테이지에 도달한 사람 = i번째 스테이지를 클리어한 사람
// (i번째 스테이지에 도달한 사람 - i번째 스테이지를 클리어한 사람) / i번째 스테이지에 도달한 사람
// i번째 스테이지에 있는 사람 / i번째 스테이지에 도달한 사람
float failure_rate(vector<int>& reached_users, int i)
{
    if (reached_users[i])
        return (reached_users[i] - reached_users[i + 1]) / (float)reached_users[i];
    else
        return 0.0f;
}

vector<int> solution(int N, vector<int> stages)
{
    vector<int> answer(N);
    vector<int> reached_users(N + 2, 0);

    for (int i = 1; i <= N; ++i)
        answer[i - 1] = i;

    // 각 스테이지별 도달한 사람 수 계산
    for (int stage : stages)
        for (int i = 1; i <= stage; ++i)
            ++reached_users[i];

    // 실패율을 기준으로 정렬
    // answer의 원소들이 인덱스를 뜻하므로 reached_users에 전달해 실패율을 기준으로 정렬할 수 있다.
    auto func = [&reached_users](int a, int b) { return failure_rate(reached_users, a) > failure_rate(reached_users, b); };
    stable_sort(answer.begin(), answer.end(), func);

    return answer;
}