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

프로그래머스의 실패율(Lv1) 문제이다.

 

[ 문제풀이 ]

게임에 존재하는 모든 스테이지와 현재 사용자들이 도전중인 스테이지가 주어지고, 실패율을 구하는 식이 주어졌을 때, 실패율이 높은 순으로 스테이지를 구해야 하는 문제이다.

간단한 변수 설정을 통해서 실패율과 스테이지 그리고 정답을 도출하는 과정까지 진행해보자.

 

#1. 실패율과 스테이지

먼저 정답을 구하기 위해서 우리가 알아야 할 정보가 무엇이 있는지 부터 알아보자.

아마 다음과 같이 2가지 정보가 필요할 것이다.

1. 각 스테이지별 실패율

2. 각 스테이지의 번호

각 스테이지별 실패율을 알고 있어야 정답을 구할 수 있고, 실질적으로 정답을 출력을 할 때에는 실패율을 출력하는 것이 아닌 실패율이 높은 순서부터 낮은 순서대로 출력을 해야 한다. 따라서 스테이지의 번호까지 알고 있어야 한다.

본인은 실패율과 스테이지를 하나의 쌍으로 관리해 주었다. 즉, pair<double, int>를 자료형으로 가지는 vector를 하나 선언해서 실패율과 스테이지를 관리해 주었다.

실패율은 소수점이 나올 수 있으므로 double형으로 선언해 주었고, int형 자료에는 스테이지를 넣어 주었다.

즉 ! 우리는 각 스테이지 별로 실패율을 구한 후, { 실패율 , 스테이지 번호 } 로 vector에 넣어줄 것이다.

그리고 이 vector를 조건에 맞게 정렬만 시켜준다면 쉽게 정답을 구할 수 있을 것이다.

 

#2. 실패율 구하기

실패율을 구하는 공식은 "스테이지에 도달했으나 아직 클리어 하지 못한 플레이어 수 / 스테이지에 도달한 플레이어 수" 가 된다.

즉 ! 실패율을 구하기 위해서는 위의 2가지 정보가 필요하다.

그런데 ! 여기서 "스테이지에 도달한 플레이어 수" 에 대해서 생각을 해보자.

만약 현재 실패율을 구하고자 하는 스테이지가 '2'단계라고 가정해보자. 그리고 각 플레이어가 도달한 스테이지가 [ 1 , 2 , 2 , 3 , 4 ] 라고 가정해보자. 그럼 여기서 스테이지에 도달한 플레이어 수는 몇 명이 될까 ??

총 4명이 된다. 현재 스테이지 2를 진행중인 플레이어도 결국 스테이지에 도달하긴 했으므로 스테이지에 도달한 플레이어에 속하게 된다. 동시에 ! 스테이지 2를 진행중인 플레이어는 스테이지에 도달했으나 아직 클리어 하지 못한 플레이어 수에도 포함되어진다.

이 부분만 주의를 해주면 된다.

 

#2에서 구한 실패율을 바탕으로 실패율과 스테이지를 한 쌍으로 vector에 삽입 해서, 이 vector를 정렬하게 되면 답을 구할 수 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool Cmp(pair<double, int> A, pair<double, int> B)
{
    if (A.first >= B.first)
    {
        if (A.first == B.first)
        {
            if (A.second < B.second)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
vector<int> solution(int N, vector<int> stages) 
{
    vector<int> answer;
    vector<pair<double, int>> Fail;
    for (int i = 1; i <= N; i++)
    {
        int Cur_Stage = i;
        int Clear_Num = 0;
        int Progress_Num = 0;
        for (int j = 0; j < stages.size(); j++)
        {
            if (stages[j] >= Cur_Stage) Clear_Num++;
            if (stages[j] == Cur_Stage) Progress_Num++;
        }
        if (Clear_Num == 0) Fail.push_back(make_pair(0, Cur_Stage));
        else
        {
            double FailPercent = (double)Progress_Num / (double)Clear_Num;
            Fail.push_back(make_pair(FailPercent, Cur_Stage));
        }
    }
    sort(Fail.begin(), Fail.end(), Cmp);
    for (int i = 0; i < Fail.size(); i++) answer.push_back(Fail[i].second);
    return answer;
}