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

 

슈퍼 게임 개발자 오렐리의 위기를 도와줘야 하는 문제

나도 되고 싶다...

슈퍼 게임 개발자...

 

---

문제의 조건

 

1. 전체 스테이지의 개수 N, 현재 플레이어들이 멈춰 있는 스테이지를 나타낸 배열 stages가 주어진다. 

 

2. 실패율이 높은 스테이지부터 내림차순으로 정렬한 배열을 리턴하는데 

실패율이 같으면 낮은 스테이지가 앞에 옴 

 

3. 스테이지에 도달한 유저가 없으면 해당 스테이지의 실패율은 0 이다.

 

4. 실패율은

스테이지에 도달했으나 클리어하지 못하고 머물러 있는 플레이어의 수 / 스테이지를 클리어 한 플레이어의 수

로 구할 수 있다. 

[1, 4, 4] 배열에서 

1 스테이지의 실패율은 1/3

2 스테이지의 실패율은 0/2

3 스테이지의 실패율은 0/2

4 스테이지의 실패율은 2/2 이 된다.

↑

이것들을 실패율에 따라 내림차순으로 정렬해서 배열에 담아 리턴하면 됨 

 

※ 여기서 N번째 스테이지까지 모든 스테이지에 대해서 실패율을 구해야 하기 때문에

만약 stages 배열에서 2 스테이지에 머물러 있는 플레이어가 없어도 2 스테이지에 대한 실패율을 구해야 한다.

그렇기 때문에 최종적으로 실패율을 구하는 반복문은 i = 1부터 시작해서 i가 N보다 같거나 작을 때까지 돌아야 함 

---

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

using namespace std;

//스테이지별 실패율을 내림차순으로 정렬하기 위한 비교 함수 
bool compare(const pair<int, float>& a, const pair<int, float>& b)
{
    //두 value가 같으면 key값이 작은 것이 앞으로 오기 
    if (a.second == b.second) return a.first < b.first;
    //아니면 value가 큰 것이 앞으로 오기 
    return a.second > b.second;
}

vector<int> solution(int N, vector<int> stages) {
    map<int, int> mapFailStage;
    for (auto& player: stages)
    {
        //스테이지별 머물러 있는 플레이어 횟수 카운트 
        auto it = mapFailStage.find(player);
        if (mapFailStage.end() == it)
            mapFailStage.insert(pair<int, int>(player, 1));
        else
            it->second++;
    }

    float Players = stages.size();
    float FailRate;
    map<int, float> mapFailRate;
    for (int i = 1; N >= i; i++)
    {
        auto it = mapFailStage.find(i);
        if (mapFailStage.end() != it)
        {
            //현재 스테이지에 멈춰있는 플레이어가 있으면 그에 대한 실패율 구하기 
            FailRate = it->second / Players;
            //다음 스테이지에 대한 실패율을 구하려면 현재 멈춰있는 플레이어 수를 총 플레이어 수에서 빼줘야 함
            Players -= it->second;
        }
        else
            FailRate = 0; //멈춰있는 플레이어가 없으면 해당 스테이지 실패율 0

        //새로운 map에 스테이지와 실패율 저장 
        //실패율이 같은 경우가 생길 수도 있으니까 key값은 스테이지 번호로 함 
        mapFailRate.insert(pair<int, float>(i, FailRate));
    }

    //실패율 내림차순으로 정렬해준다.  
    vector<pair<int, float>> vec(mapFailRate.begin(), mapFailRate.end());
    sort(vec.begin(), vec.end(), compare);

    vector<int> answer;
    for (auto rate: vec)
        answer.emplace_back(rate.first);

    return answer;
}

 

쬐끔 시간이 걸렸지만...

답 안 찾아보고 스스로 생각한 알고리즘으로 풀어서 좋아요!