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

문제 설명

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

(실패율) = (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수) / (스테이지에 도달한 플레이어 수)

주요 로직

1. 정렬 알고리즘 사용

시간 복잡도가 O(NlogN)인 sort() 메서드를 사용하였다. cmp라는 비교함수를 매개 변수로 넣어 pair<double, int> 에 대한 내림차순으로 정렬할 수 있도록 하였다.

 

2. 예외 생각히기

원래는 아래와 같이 코드를 작성했었는데 5개의 TC에 대해서 실패가 떴다. 알고보니 num 값이 0이 되는 경우를 배제하여서 Divided by zero 오류가 난 것이었다. 따라서 num이 0이 되는 경우에 실패율을 그냥 0으로 넣어줬더니 해당 TC를 통과한다 (아래 정답 코드 참고)

for(int i=1; i<=N; i++){
    fail.push_back({(double)people[i]/num, i});
    num -= people[i];
}

 

정답 코드

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

bool cmp(pair<double, int> a, pair<double,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> people(N+1, 0);  // 각 스테이지에 존재하는 사람 수
    vector<pair<double, int>> fail;  // <실패율, 스테이지> 
    sort(stages.begin(), stages.end());
    for(auto stage : stages){
        people[stage]++;
    }
    int num = stages.size();
    for(int i=1; i<=N; i++){
        if(num == 0)
            fail.push_back({0,i});
        else
            fail.push_back({(double)people[i]/num, i});
        num -= people[i];
    }
    
    sort(fail.begin(), fail.end(), cmp);
    for(auto it : fail){
        answer.push_back(it.second);
        cout << it.first << " " << it.second << "\n";
    }
    
    return answer;
}