프로그래머스 실패율 cpp

1. 문제

실패율이 높은 스테이지부터 내림차순을로 스테이지 번호가 담긴 배열을 return한다.

 

2. 설계

(1) 게임을 이용하는 사용자의 수 stages.size()를 p라고 했을 때,

낮은 스테이지부터, (현재 보고 있는 스테이지에 있는 사람)/(전체 사람 수 중 이전 스테이지까지 있었던 사람)을 구하면 각 스테이지 별 실패율이 나온다.

(2)스테이지번호와 실패율을 pair로 만들 {(1-실패율), stage넘버} 한 후 sort한다. 1-실패율을 넣는 이유는, 실패율은 높은 숫자 먼저(내림차순) , 같은 실패율에 대해서는 stage를 낮은 숫자에서 높은 숫자로(올림차순)으로 정렬해야하기 때문에 둘 중 하나를 바꿔서 정렬해야하기 때문이다.

 

3. 알고리즘

 

4. 구현: 정답코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int p = stages.size(); //전체사람수
    map<int,int> mp; // stage에 있는 사람 수를 세기 위한 hash
    for(auto iter: stages){
        mp[iter]++;
    }
    vector<pair<double,int>> failV; //실패율과 stage를 넣을 vector
    for(int i=1; i<=N; i++){
        double failP = (mp[i]/(double)p); //실패율
        p-=mp[i]; // 다음으로 넘어간 사람의 수
        failV.push_back({(1-failP), i}); 
    }
    sort(failV.begin(), failV.end()); //정렬
    for(auto iter: failV){
        answer.push_back(iter.second);
    }
    return answer;
}