[카카오 2019 BLIND RECRUITMENT] 실패율 (프로그래머스)

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

코딩테스트 연습 - 실패율

[카카오 2019 BLIND RECRUITMENT] 실패율 - 프로그래머스 문제

 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    priority_queue<pair<double,int> > pq;

    for(int sn=1;sn<=N;sn++) {
        double finUser=0.0;
        double curUser=0.0;

        for(int i=0;i<stages.size();i++) {
            if(stages[i]==sn) {
                curUser+=1;
            }

            if(stages[i]>sn) {
                finUser+=1;
            }
        }

        double ans=(double)curUser/((double)curUser+(double)finUser);

        pq.push({ans,-sn});
    }
    
    while(!pq.empty()) {
        answer.push_back(-pq.top().second);
        pq.pop();
    }

    return answer;
}

 

실패율 조건이나 입,출력 양식은 다른 문제에 비해 비교적 간단한 편이다.

아마도 어려운 부분은 실패율을 내림차순 정렬해서

그 '실패율 순서에 해당하는 스테이지 번호를 어떻게 answer 벡터에 담아 리턴하느냐' 인 것 같다.

 

이 부분은 우선순위 큐를 이용하면 간단히 해결된다.

이러면 실패율은 내림차순으로 잘 적용되는데 스테이지 번호까지 내림차순이 되어 문제 출력 조건에 부합하지 않게 된다.

 

해결책은 이렇다.

실패율은 그대로 push하되,

스테이지 번호는 마이너스( - ) 를 씌워서 push하고 꺼낼 때도 다시 마이너스( - ) 부호를 씌우면 된다.