[프로그래머스] 1단계 - 실패율

문제 설명

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

프로그래머스

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개 변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return하기

 

문제 풀이법

단순 구현이기에 문제에서 설명하는대로 잘 구현하면 된다

여기서 몇가지 주의 해야할 점이 있는데

• N + 1의 스테이지에 도달한 사람은 N번째 스테이지까지 클리어한 사람이다
  • => 따라서 N번째 스테이지에 도달한 사람일때만 개수 count를 해주고, 나머지 연산에서는 필요없다
  • 괜히 N + 1까지 for문을 돌았다가 오류가 생긴다
  • 문제에서 원하는 것은 N까지!
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 한다

 

구현 순서

• 실패한 사람의 수, 스테이지에 도달한 사람 수를 구하기 위한 vector을 선언한다.
• stages.size()만큼 돌면서 해당 스테이지의 실패한 사람의 수와, 도달한 사람의 수를 구한다
  • j < N && j < stages[i]를 조건으로 두어 효율적으로 for문을 돌도록 했다
  • (j + 1) <= stage[i]이면 해당 스테이지에 도달한 사람을 + 1 해주었다
  • (j + 1) == stage[i]이면 해당 스테이지에 도달했지만 실패했으므로, 추가로 해당 스테이지를 실패한 사람의 수 + 1 해주었다 
• pair를 사용해 해당 스테이지와, 스테이지의 실패율을 담을 vector를 선언하여 담는다
• sort를 사용해 문제에서 원하는 대로 정렬한다
  • cmp 함수를 커스텀하여 사용
  • 실패율이 같으면, 스테이지 번호를 오름차순
  • 실패율이 다르면, 실패율을 내림차순
• sort된 vector를 돌면서 최종적으로 answer에 스테이지 번호를 담는다  

 

테스트케이스 2번은 되는데, 1번은 [1, 2, 3, 4, 5]로 오류가 난다! 하시는 분

=> 실패율을 구하는 유심히 보시길 바랍니다

"실패한 사람 수 / 도달 한 사람 수" 를 그냥 하게 되면 정수형으로 연산이 됩니다

하지만 우리가 원하는 것은 float 형이므로 앞에 (float)를 붙여주면 성공할 수 있습니다 

 

소스 코드

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

using namespace std;

bool cmp(pair<float, int> a, pair<float, int> b)
{
    if (a.first == b.first)
        return a.second < b.second;
    return a.first > b.first;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    vector<int> fail(N);
    vector<int> player(N);
    
    
    for (int i = 0; i < stages.size(); i++)
    {
        for (int j = 0; j < N && j < stages[i]; j++)
        {
            if ((j + 1) <= stages[i])
            {   
                player[j]++;
                if ((j + 1) == stages[i])
                    fail[j]++;
            }
        }
    }
    
    
    vector<pair<float, int>> v;
    for (int i = 0; i < N; i++)
    {
        if (player[i] == 0)
            v.push_back({0, i + 1});
        else
            v.push_back({((float)fail[i] / player[i]), i + 1});
    }
    
    sort(v.begin(), v.end(), cmp);
    
    for (int i = 0; i < v.size(); i++)
    {
        answer.push_back(v[i].second);
    }
    
    return answer;
}