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

(주)그렙

[programmers] 프로그래머스 실패율

(C++)

(글쓴날 : 2020.06.06)

 

---

* programmers, 프로그래머스 문제 C++ 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 실패율

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

총 스테이지 수와 유저들이 머무르고 있는 스테이지가 주어질 때 스테이지별 실패율이 높은 순서를 구하는 문제입니다.

단, 실패율이 같을 경우 작은 번호의 스테이지가 앞에 옵니다.

 

저의 경우, C++을 사용했습니다.

스테이지별 머무르고 있는 유저 수와 스테이지 번호를 저장하고 있는 pair 형태의 해시 vetor를 만들어 실패율을 구한 뒤, 요구 조건에 맞춰 정렬하여 문제를 해결했습니다.

주의해야 할 점이 한 가지 있는데 만약, 어떤 스테이지에 아무 유저도 도달하지 못했을 경우 0으로 나눠버리게 되므로 해당 부분을 조건문으로 체크하여 예외 처리해 주셔야 합니다.

---

3) 코드

 

* C++ 코드

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
 
using namespace std;
 
bool compare(const pair<double, int> &a, const pair<double, int> &b)
{
    if (a.first == b.first)
    {
        if (b.second > a.second)
            return true;
        else
            return false;
    }
    else if (a.first > b.first)
        return true;
    else
        return false;
}
 
vector<int> solution(int N, vector<int> stages)
{
    vector<int> answer;
 
    vector<pair<double, int>> location;
 
    for (int i = 0; i < N + 2; i++)
        location.push_back({0, i});
 
    for (int i = 0; i < stages.size(); i++)
        location[stages[i]].first += 1.0;
 
    double people = stages.size();
    for (int i = 1; i < N + 1; i++)
    {
        double now = location[i].first;
        if (now == 0.0)
        {
            location[i].first = 0.0;
            continue;
        }
 
        people -= now;
 
        location[i].first = now / people;
    }
 
    sort(location.begin() + 1, location.end() - 1, compare);
 
    for (int i = 1; i < N + 1; i++)
        answer.push_back(location[i].second);
 
    return answer;
}

---