공부흔적

문제 링크

풀이 )

  처음 stages 배열을 한바퀴 돌아 각 스테이지에서 실패한 인원을 저장한 배열 fail에 저장을 한다.

  이후 각 스테이지에서의 실패율을 계산한다.

  이 때 현재 스테이지에 올라온 인원을 저장하는 변수 clear에 저장하고 실패한 인원 수 만큼 매번 빼준다.

  이후 실패율을 내림차순으로 정렬하여 실패율이 높은 순서대로 스테이지를 answer 벡터에 집어넣는다.

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

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> fail(N, 0);
    vector<pair<int, double>> rate;
    int clear = stages.size();
    
    for(vector<int>::iterator it = stages.begin(); it != stages.end(); ++it){
        if(*it == N+1)
            continue;
        fail[(*it)-1]++;
    }   // 각 스테이지 실패 인원 수
    
    int stage = 1;
    for(vector<int>::iterator it = fail.begin(); it != fail.end(); ++it){
        rate.push_back(make_pair(stage++, clear == 0 ? 0 : ((double)*it)/clear));
        clear -= *it;
    }   // 각 스테이지 실패율
    
    sort(rate.begin(), rate.end(), [](auto &left, auto &right){
        if(left.second == right.second)
            return left.first < right.first;
        return left.second > right.second;
    }); // 실패율 정렬
    
    for(vector<pair<int, double>>::iterator it = rate.begin(); it != rate.end(); ++it)
        answer.push_back((*it).first);
    return answer;
}

주의점 )

• 클리어한 인원 수가 0일 때, 0으로 나눌 수 없기 때문에 실패율은 0
• 실패율을 정렬할 때 실패율이 같은 경우 스테이지 정렬