[프로그래머스] 실패율

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

코딩테스트 연습 - 실패율

---

 

-풀이-

1. 먼저 각 스테이지당 몇명이 도달했지만 클리어 하지 못했는지 구한다.

 

2. vector<pair<double,int>> v를 선언한다. double=실패율, int=층수

 

3. 1층~N층까지 층을 돌며, 해당 층의 실패율을 구한다.

 

만약 해당 층을 클리어하지 못한사람이 없으면 {0,층수}를 푸쉬해주고,

있다면, {클리어하지 못한사람/사람의 수, 층수} 를 push 해준뒤, 다음 층의 실패율을 위해 사람의 수에서 클리어하지 못한사람의 수를 빼준다.

 

EX) 전체사람수=8, 1층을 클리어하지 못한사람 = 1명 이라면, 1층의 실패율은 1/8 이 될것이다. 다음 층부터는 1층을 클리어하지 못한사람을 고려하지 않아야 하므로, 사람의 수를 8-1=7로 갱신해준다.

 

4. 그런뒤 v를 정렬한다. 1순위로는 실패율값을 기준으로 내림차순 정렬하고, 2순위로는 층수를 기준으로 오름차순 정렬을 해준다.

 

5. v에 저장되어있는 층수를 순차적으로 answer에 넣어준다.

 

-시간복잡도-

스테이지의 개수를 N, stages벡터의 길이를 M이라고 한다면, 1번을 동작시킬때 O(M) , 3번을 동작시킬땐 O(N), 정렬은 O(NlogN), 마지막으로 5번은 O(N)시간이 걸린다. N은 1~500, M=1~200000 이므로, 최종 시간복잡도는 O(M)이 된다.

 

-코드-

 

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
bool compare(pair<double,int> a, pair<double,int> b){
    if(a.first==b.first){
        return a.second<b.second;
    }
    else{
        return a.first>b.first;
    }
}
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double,int>> v;
    int people=stages.size();
    int stay[200001]={0};
    for(int i:stages){
        stay[i]++;
    }
    
    for(int i=1;i<=N;i++){
        if(!stay[i]){
            v.push_back({0,i});
        }
        else{
            v.push_back({(double)stay[i]/people,i});
            people-=stay[i];
        }
    }
    sort(v.begin(),v.end(),compare);
    for(auto i:v){
        answer.push_back(i.second);
    }
    return answer;
}