[Lv 1] 실패율

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

 

이 문제는 배열 순회를 통해 해결할 수 있다.

문제에서 스테이지의 개수는 N을 통해 제공된다.

따라서 1스테이지 부터 N 스테이지 까지 반복을 진행해야함을 알 수 있었다.

 

스테이지에 도달하였지만 아직 클리어 하지 못한 플레이어 수는 현재 순회하고 있는 스테이지 번호와 같은 플레이어의 수를 새면 알 수 있다.

따라서 vector의 내장 함수인 count를 통해 알아 낼 수 있다.

 

실패율은 아직 클리어하지 못한 플레이어 수 / 스테이지에 도달한 플레이어 수를 구하면 알 수 있다.

따라서 나중에 내림차순을 하기 위해 vector에 현재 스테이지 번호와 함께 실패율을 삽입한다.

 

마지막으로 스테이지에 도달한 플레이어 수를 구하기 위해서는 

스테이지 배열의 크기와 이전에 구한 아직 클리어하지 못한 플레이어 수를 빼면 알 수 있다.

또한 분모가 0이 되는 경우는 나눴을 때 문제가 되기 때문에 0이 되는 경우는 실패율을 0으로 하여 배열에 삽입한다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double, int>> failure;
    int noClearStage;
    int noReachStage = 0;
    
    for (int i=1; i<=N; i++) {
        int noClearStage = count(stages.begin(), stages.end(), i);
        
        if (stages.size() == noReachStage) {
            failure.push_back({0, i});
            continue;
        }
        
        failure.push_back({(double)noClearStage / (double)(stages.size() - noReachStage), i});
        noReachStage += noClearStage;
    }
    
    sort(failure.begin(), failure.end(), cmp);
    
    for (int i=0; i<failure.size(); i++) {
        answer.push_back(failure[i].second);
    }
    
    return answer;
}