프로그래머스, 실패율 카카오 (C++)

프로그래머스

출처는 프로그래머스이다.

문제는 다음 링크를 타고 들어가면 확인할 수 있다. ( programmers.co.kr/learn/courses/30/lessons/42889 )

 

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
/*
N    stages    result
5    [2, 1, 2, 6, 2, 4, 3, 3]    [3,4,2,1,5]
4    [4,4,4,4,4]    [4,1,2,3]
*/
 
bool CmpPair(const pair<int, double>& i, const pair<int, double>& j)
{
    if(i.second == j.second)
        return i.first < j.first;
    return i.second > j.second;
}
 
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> stage_fcnt; 
    // 각 스테이지 별로 몇 명 통과했는지를 기록 | [0]은 1번 스테이지, [1]은 2번 스테이지 ...
    vector<pair<int, double>> failpair;
    // 각 스테이지 별 실패율이 어떤 지를 확인.
    // 이렇게 묶어두면 정렬하기가 매우 편리하다.
    
    // 스테이지의 갯수만큼 벡터 요소들 추가한다.
    for(int i=0; i<N; i++)
        stage_fcnt.push_back(0);
    
    // 각 스테이지 별로 몇 명 묶여 있는지 파악.
    for(vector<int>::iterator it=stages.begin(); it!=stages.end(); it++)
        if(*it < N+1) // 1부터 N 스테이지의 실패율만 알면 되기 때문에.
            stage_fcnt[*it-1]++;
    
    // 각 스테이지 별 실패율을 구한다.
    for(int i=0, now_cnt=stages.size(); i<stage_fcnt.size(); i++)
    {
        if(stage_fcnt[i] == 0) // 스테이지를 아무도 묶여 있지 않다면
            failpair.push_back(make_pair(i+1, 0)); // 그냥 0 처리하며 now_cnt는 줄이지 않는다!!
        else 
        {
            failpair.push_back(make_pair(i+1, (double)stage_fcnt[i] / (double)now_cnt));
            now_cnt-=stage_fcnt[i];        
        }
                               
    }
 
    // 정렬을 하되 CmpPair 조건에 맞도록 정렬한다.
    sort(failpair.begin(), failpair.end(), CmpPair);
    
    // 실패율을 기준으로 pair를 정렬했으니 pair 중 stage에 해당하는 값만 answer에 저장.
    for(vector<pair<int, double>>::iterator it=failpair.begin(); it != failpair.end(); it++)
        answer.push_back(it->first);
    
    return answer;
}