C++ / 프로그래머스 / 실패율

문제

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

코딩테스트 연습 - 실패율

문제풀이

실패율은 스테이지를 클리어 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수이다.

여기서 i 스테이지를 클리어 못한 플레이어의 수는 stages벡터에서 i의 개수이고,

스테이지에 도달한 플레이어의 수는 i 스테이지를 지나간 플레이어의 수이다.

1번 스테이지의 경우 stages벡터에 1은 1개이고, 1 이상인 수가 8개이므로 실패율이 1/8이다.

 

    for (idx = N; idx > 0; --idx)
        pass[idx] = now_stage[idx] + pass[idx + 1];

따라서 메모이제이션을 이용하여 도달한 플레이어의 수를 구한다.

 

실패율과 해당 스테이지를 저장하는 벡터를 pair로 선언하여 2열만 있는 벡터를 만든다.

스테이지는 1 스테이지부터 있기 때문에 1부터 N까지 반복문을 돌아 실패율을 저장한다.

이때 분모가 0이면 안되므로 0일 때 조건을 걸어준다.

bool compare(pair<double, int> a, pair<double, int> b) {
    return a.first > b.first;
}

    stable_sort(failure_late.begin(), failure_late.end(), compare);

실패율을 내림차순으로 정렬하고, 실패율이 같을 때는 오름차순으로 정렬해야 된다.

위에서 for문을 돌릴 때 오름차순으로 돌렸기 때문에 stable_sort를 이용하여 첫 번째 숫자만 비교하여 실패율은 내림차순으로, 인덱스는 오름차순으로 정렬한다.

그다음 idx만 answer에 push 하여 출력한다.

 

 

코드

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

using namespace std;

bool compare(pair<double, int> a, pair<double, int> b) {
    return a.first > b.first;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> now_stage(N + 2, 0);
    vector<int>pass(N + 2, 0);

    int idx = 0;
    for (idx = 0; idx < stages.size(); ++idx)
        now_stage[stages[idx]]++;

    pass[N + 1] = now_stage[N + 1];

    for (idx = N; idx > 0; --idx)
        pass[idx] = now_stage[idx] + pass[idx + 1];

    vector<pair<double, int>> failure_late;

    for (idx = 1; idx <= N; ++idx) {
        if (pass[idx] != 0)
            failure_late.push_back({ (double)now_stage[idx] / pass[idx], idx });
        else
            failure_late.push_back({ 0, idx });
    }

    stable_sort(failure_late.begin(), failure_late.end(), compare);

    for (idx = 0; idx < N; ++idx)
        answer.push_back(failure_late[idx].second);

    return answer;
}