[프로그래머스] 실패율

프로그래머스: 문제

코딩테스트 연습 - 실패율

문제를 보자마자 뚝딱뚝딱 풀다가 한 번에 통과해낼 수 있었다.

구간별 합까지는 필요 없기에 Prefix Sum까지는 접근할 필요가 없다. 하지만 이전과 달리 뒤에서부터 누적적으로 더해야만 해당 스테이지별 도달한 플레이어 수를 알 수 있다.

예를 들어 간단하게 총 4개의 스테이지가 있다고 할 때 stages 배열이 [2,3]이라고 한다면 각 스테이지별 도달 플레이어수는 스테이지1부터 [2,2,1,0]이다. 이를 구하기 위해서는 평소와 다르게 뒤에서부터 뒤 스테이지에서 클리어하지 못한 플레이어를 앞선 스테이지는 클리어했다는 것을 전제로 해서 앞 스테이지 도달자로 반영된다. 이는 stage[i] += stage[i + 1]라는 점화식으로 풀어낼 수 있다. 

여기서 주의해야할 점은 이미 끝난 사람은 스테이지 개수 + 1로 처리한다는 점이다. 이것을 반드시 감안해서 코드에 반영해야 한다.

 

또한 반드시 로직 다 짜놓고, 코드적으로 실수하지 않아야 한다..ㅠ cmp 비교함수에서 return으로 끝내지 않아서 오름차순, 내림차순이 제대로 반영되지 않았다... 후... 왜 로직이 이상하게 나오는지 약간 헤맸다. 정신차리자!

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int stage[502] = {0};
vector<pair<double, int>> fails;
bool cmp(const pair<double, int> a, const 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;
    for(int i = 0;i < stages.size();i++){
        int s = stages[i];
        stage[s]++;
    }
    // 이미 끝낸 사람 포함
    for(int i = N + 1;i > 0;i--){
        stage[i - 1] += stage[i];
    }
    for(int i = 1;i <= N;i++){
        if(!stage[i]) fails.push_back({0,i});
        else fails.push_back({(double)(stage[i] - stage[i + 1]) /stage[i], i});
    }
    sort(fails.begin(), fails.end(), cmp);
    
    for(int i = 0;i < N;i++){
        answer.push_back(fails[i].second);
    }
    return answer;
}