프로그래머스 실패율

 

글이 복잡하게 쓰여있지만 이해하기 그리 어렵지 않다.

result에 실패율이 높은 순으로 정렬해서 return 해주면 되는데 어떻게 실패율을 구할 것인가가 중요하다

우선 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 인데

현재 스테이지 개수 / 현재보다 크거나 같은 스테이지의 개수로 치환 가능하다.

 

따라서 전처리를 통해 stages의 원소들이 몇 번 등장했는지와 가장 큰 값을 구해놓는다.

가장 큰 값은 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다. 조건 때문에 필요한데

for 문을 돌리면서 i 값이 가장 큰 값보다 크다면 실패율을 0으로 push 해줘야 하기 때문이다.

 

pair벡터를 <int, double>로 선언해주는데 idx와 fail rate를 담는다.

 

첫 번째 예제를 보면

각각의 번호와 몇 번 등장했는지를 구해보면 이렇게 나오는데

스테이지의 총인원수가 8명이니

<1,1> <2,3> <3,2> <4,1> <5,0> <6,1> 

 

에서 1번의 실패율은 1의 second / n - sum(누적)이다.

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int d[501];
 
bool comp(pair<int, double>& a, pair<int, double>& b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}
 
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<int, double>> a; // idx, fail rate
    int n = stages.size();
    for (int i : stages) d[i]++;
    int m = *max_element(stages.begin(), stages.end());
    
    int sum = 0;
    for (int i = 1; i <= N; ++i) {
        if (i > m) a.push_back({ i,0 });
        else a.push_back({ i,(double)d[i]/(n - sum) });
        sum += d[i];
    }
    sort(a.begin(), a.end(), comp);
    
    for (auto i : a) answer.push_back(i.first);
    
    return answer;
}

 

정렬은 comp를 통해 쉽게 구현 가능하다.