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

문제

프로그래머스 2019 KAKAO BLIND RECRUITMENT - 실패율 (Level 1)

코딩테스트 연습 - 실패율

 

---

문제 풀이

접근 방식

이 문제는 카카오 블라인드 공채 1차 코딩테스트 2번 문제로,

게임 이용자들이 현재 멈춰 있는 스테이지 번호를 통해 실패율을 구하는 문제였다.

 

우선, 주어진 스테이지 번호를 통해 각 스테이지에 머물러 있는 이용자들의 수를 구해 cnt 벡터에 저장해주었다.

그리고 스테이지 번호와 실패율을 저장할 result 벡터을 만들어주고,

cnt 벡터를 뒤에서 부터 탐색하며 다음과 같이 실패율을 구해주었다.

 

실패율 = (현재 스테이지에 머물러 있는 이용자의 수) / (지금까지 탐색한 스테이지의 이용자 수의 합)

 

이후, cmp 함수를 구현하여 result 벡터를 실패율이 높은 순으로 정렬해주었고,

정렬된 result 벡터의 스테이지 번호를 answer에 저장하여 답을 구해주었다.

 

---

풀이 코드 - C++

#include <vector>
#include <algorithm>
using namespace std;

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

vector<int> solution(int N, vector<int> stages) {
    vector<int> cnt(N+1);
    for(int s : stages) cnt[s - 1]++;
    int sum = cnt[N];
    
    vector<pair<int, float>> result(N);
    for(int i = N - 1; i >= 0; i--) {        
        sum += cnt[i];
        result[i].first = i + 1;
        if(sum == 0) result[i].second = 0;
        else result[i].second = (float) cnt[i] / sum;
    }
    
    vector<int> answer;
    sort(result.begin(), result.end(), cmp);
    for(auto r : result) answer.push_back(r.first);
    return answer;
}

실행 결과

실행 결과 : 100.0