[C++] 프로그래머스 실패율

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

using namespace std;

bool sortSolve(pair<float, int> a, pair<float, int> b);

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;

    map<int, int> stageNon;
    map<int, int> stageClear;

    vector<pair<float, int>> nonClear; //실패율

    for (int i = 0; i < N; i++) //스테이지만큼 생성
        stageNon[i] = 0;

    for (int i = 0; i < stages.size(); i++)
    {
        for (int j = 0; j < stages[i]; j++)  //스테이지 도달과 클리어의 인원 적용
        {
            if (N >= stages[i] && j == 0)
                stageNon[stages[i]]++;

            if (j > 0)
                stageClear[stages[i] - j]++;
        }
    }

    for (int i = 1; i <= N; i++)
    {
        float tempSum = stageNon[i] + stageClear[i]; //스테이지에 진입했던 사람들
        float tempSol = stageNon[i] / tempSum; //실패율의 계산

        if (stageNon[i] == 0)    //도달이 없을 경우 0퍼
            tempSol = 0;

        nonClear.push_back({ tempSol, i });
    }

    sort(nonClear.begin(), nonClear.end(), sortSolve);

    for (int i = 0; i < N; i++)
        answer.push_back(nonClear[i].second);

    return answer;
}

bool sortSolve(pair<float, int> a, pair<float, int> b)	//정렬조건
{
    if (a.first == b.first)
        return a.second < b.second;

    return a.first > b.first;
}

풀이

1. 스테이지 도달인원과 스테이지 클리어인원을 저장한다.

2. 스테이지 도달인원중 N을 넘는 인원은 클리어인원으로 한다.

(N+1이므로 스테이지도달인원을 빼고 클리어인원에만 저장)

3. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수( 클리어인원과 스테이지인원의 합 )을 구한다. 

4. 조건의 내용처럼 실패율이 같으면 낮은 스테이지가 우선으로한다. 그외는 실패율이 큰 순으로한다.

 

- for문을 줄이고 map을 덜 사용하면 더 효율성이 좋아질듯하다.

 

 

 

 

 

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

코딩테스트 연습 - 실패율