(C++) - 프로그래머스(2019 KAKAO BLIND RECRUITMENT) : 실패율

programmers.co.kr/learn/courses/30/lessons/42889?language=cpp#

코딩테스트 연습 - 실패율

간단한 구현문제였습니다.

 

풀이방법

 1. map에 스테이지별로 도전하고 실패한 사람을 세줍니다. (key,value) = (스테이지, 실패자 수) 입니다.

 

 2. 실패율을 구해 vector 변수에 loseRatio 저장합니다. 실패율은 다음과 같습니다. 스테이지 i-1까지 도전한 사람들의 누적 수를 구해줍니다. 현재 스테이지 / (총 인원 - 누적 수)가 곧 i번 스테이지의 실패율이 됩니다. 이 때 총 인원 - 누적 수가 0이하가 되면 실패율을 0으로 만들어 줍니다.

 

 3. 실패율이 높은 순으로, 스테이지가 작은 순으로 sort해줍니다.

 

 4. 정렬된 스테이지들을 answer에 push_back해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pdi = pair<double,int>;
bool cmp(pdi &a, pdi &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 <pdi> loseRatio;

    int accumulate = 0;
    int people = stages.size();
    map<int,int> loser;
    for(auto &s : stages) loser[s]++;

    for(int i = 1; i<=N; i++){
        double loseRate = (double)loser[i] / (double)(people - accumulate);
        if(people - accumulate <= 0) loseRate = 0;
        loseRatio.push_back({loseRate,i});
        accumulate += loser[i];
    }

    sort(loseRatio.begin(),loseRatio.end(),cmp);
    for(auto &l : loseRatio) answer.push_back(l.second);
    return answer;
}

 

Test Case

몇 가지 반례를 작성해보았습니다.

5, [2, 1, 3, 5, 6, 6, 6]

[5, 3, 2, 1, 4]

 

5, [1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4]

[4, 3, 2, 1, 5]