코딩테스트 : 실패율

문제 요약
해당 문제는 각 스테이지별로 실패율을 계산한 후, 실패율이 높은 순서대로 스테이지 번호를 정렬해 반환하는 문제이다.

 

핵심 방법

유저들이 멈춰있는 스테이지 정보를 기반으로 실패율을 계산해야 하므로, 각 스테이지에 도달한 유저 수와 실패한 유저 수를 따로 구해야 한다.

실패율이 같은 경우 스테이지 번호가 작은 순서대로 정렬해야 하므로, pair<스테이지 번호, 실패율> 형태로 저장 후 정렬 기준을 커스터마이징 해야 한다.

 

구현 방법

remain[i] : i번 스테이지에서 멈춰 있는 유저 수 (즉, 실패한 유저 수)

challenge[i] : i번 스테이지에 도달한 유저 수

실패율 = remain[i] / challenge[i]

실패율이 같은 경우 스테이지 번호가 작은 것이 앞에 와야 하므로 sort 정렬 조건에 이중 기준 설정

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

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> challenge(N + 1, 0); // 각 스테이지에 도달한 유저 수
    vector<int> remain(N + 1, 0);    // 각 스테이지에 도달했지만 클리어하지 못한 유저 수
    vector<int> answer;              // 최종 정답 배열
    vector<pair<int, float>> failure_rate; // {스테이지 번호, 실패율}

    // 모든 유저들의 정보를 이용해 remain과 challenge 배열 계산
    for (int stage : stages) {
        if (stage <= N) {
            remain[stage]++; // 클리어하지 못한 스테이지에 해당 유저를 카운트
        }
        // 현재 유저가 도달한 모든 스테이지에 대해 도달한 유저 수를 증가
        for (int i = 1; i <= min(stage, N); i++) {
            challenge[i]++;
        }
    }

    // 각 스테이지에 대해 실패율을 계산
    for (int i = 1; i <= N; i++) {
        if (challenge[i] == 0) {
            failure_rate.push_back({i, 0.0f}); // 도달한 유저가 없으면 실패율 0
        } else {
            failure_rate.push_back({i, static_cast<float>(remain[i]) / challenge[i]});
        }
    }

    // 실패율 기준으로 내림차순, 같으면 스테이지 번호 오름차순 정렬
    sort(failure_rate.begin(), failure_rate.end(), [](const pair<int, float>& a, const pair<int, float>& b) {
        if (a.second == b.second) {
            return a.first < b.first;
        }
        return a.second > b.second;
    });

    // 정렬된 결과에서 스테이지 번호만 추출
    for (const auto& [stage, rate] : failure_rate) {
        answer.push_back(stage);
    }

    return answer;
}