2019 KAKAO BLIND RECRUITMENT > 실패율

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

 

배열을 순회하며 이를 pair를 컨테이너로 쓰는 vector 형태의 자료구조로 변환하여 풀었다.

먼저 stages에서 주어진 각 플레이어들의 최대 도달 레벨을 각 레벨의 시점으로 변경하는 자료구조를 만들었다.

 

이는 스테이지 순서대로 순회하기 위해 만든 구조이다.

이 자료구조를 순회하면 각 stage에 도달한 사람은 다음과 같다.

 

(전체 플레이어의 수) - (이전 단계들에서 탈락한 플레이어의 수)

 

따라서 total_user의 전체 플레이어의 수를 더해준 다음 각 레벨에서 실패율을 구하고 난 다음 해당 스테이지가 마지막 도전인 플레이어들의 수만큼 제외해 주었다.

 

이렇게 구한 실패율과 해당 레벨을 pair 구조에 넣은 다음 sort 해 주어 문제를 해결하였다.

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

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> level(N + 1, 0);  // 스테이지별 도달한 사용자 수
    vector<int> users(N + 1, 0);  // 각 스테이지를 플레이한 사용자 수
    vector<pair<double, int>> failureRates; // 실패율과 스테이지 번호를 저장

    for (int stage : stages) {
        if (stage <= N) {
            level[stage]++;
        }
    }
    
    int total_users = stages.size();  // 전체 사용자 수
    for (int i = 1; i <= N; i++) {
        if (total_users == 0) {
            failureRates.push_back(make_pair(0.0, i));  // 남은 사용자가 없으면 실패율은 0
        } else {
            double failureRate = (double)level[i] / total_users;  // 실패율 계산
            failureRates.push_back(make_pair(failureRate, i));
            total_users -= level[i];  // 해당 스테이지에 도달한 사용자를 제외한 나머지 사용자의 수로 갱신
        }
    }

    sort(failureRates.begin(), failureRates.end(), [](pair<double, int> a, pair<double, int> b) {
        if (a.first == b.first) return a.second < b.second;
        return a.first > b.first;
    });

    // 정렬된 스테이지 번호를 정답에 추가
    for (auto fr : failureRates) {
        answer.push_back(fr.second);
    }

    return answer;
}