[C/C++] 프로그래머스스쿨 실패율, 정렬

문제

코딩테스트 연습 - 실패율 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

코드

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

using namespace std;

struct num{
    float users;
    float fail;
    int stage;
};

bool cmp(struct num A, struct num B){
    if (A.fail==B.fail)
        return A.stage<B.stage;
    return A.fail>B.fail;
}

vector<int> solution(int N, vector<int> stages) {
    vector<num> answer(N);
    float total = stages.size();

    for (int i = 0; i < stages.size(); i++)
        if (stages[i]<=N)
            answer[stages[i]-1].users++;

    for (int i = 0; i < N; i++) {
        if (answer[i].users<1)
            answer[i].fail=0;
        else
            answer[i].fail=answer[i].users/total;
        answer[i].stage=i+1;
        total-=answer[i].users;
    }

    sort(answer.begin(), answer.end(), cmp);
    
    vector<int> ans;
    for (int i = 0; i <N; i++)
        ans.push_back(answer[i].stage);

    return ans;
}

풀이

1. 하나의 벡터(answer)에 데이터 타입이 서로 다른 도전자 수(users), 실패율(fail), 그리고 단계(stage)를 넣기 위해 struct를 사용하였다.

2. 입력받은 stages에는 도전자들이 각각 도전중인 단계가 입력되어 있으므로 stages의 크기 자체가 전체 도전자 수(total)가 된다.

3. 단계별 도전자 수를 파악하기 위해 계수정렬을 사용하였다.answers의 인덱스+1이 곧 단계가 되고, stages[i]의 값이 곧 answer.users의 인덱스가 되어 answer의 인덱스=i인 곳의 값을 1씩 증가시킨다.

4. 3번 과정을 진행할 때, stages의 값이 N+1인 곳은 모든 단계를 통과한 사용자이므로 스킵한다.

5. 실패율을 계산할 때에는 같은 행에 있는 도전자 수를 total로 나눈다. 단계가 하나씩 올라갈 때마다 total에서 이전 단계에 도전중인 사용자는 제외한다. 이 과정에서 같은 행에 stage(i+1)를 입력한다

6. cmp함수를 사용하여 실패율이 높은 순으로, 다만 실패율이 같은 경우 단계순으로 정렬한다.

7. 1차원 벡터 ans에 answer의 stage를 입력한후 return ans