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

문제

문제에서 추출해야 하는 정보는 다음과 같다.

• stages는 1~N+1까지의 자연수가 담겨있다. 이는 현재 도전 중인(도달한) 스테이지이며, N+1은 N번째 스테이지까지 모두 클리어한 사용자를 나타낸다.
• 실패율의 내림차순으로 각 스테이지를 정렬한다.
• 만약 두 스테이지의 실패율이 같다면 인덱스가 작은 순으로 나열한다.
• 스테이지에 도달한 유저가 없으면 실패율은 0이 된다.

입출력

유저들의 현재 스테이지가 인자를 통해 전달되면, 각 스테이지별 통과 여부와 도달 여부를 계산하여 이를 나눈 결과를 정렬하는 문제이다.

2단계에 도달한 유저는 그 값이 2보다 크거나 같다.
2단계를 통과하지 못한 유저는 그 값이 2이다.
즉 실패율[2] = (2인 경우의 수 / 2보다 크거나 같은 경우의 수)이다.

스테이지별 실패율을 차례대로 계산하여 저장하자.
소수점까지 계산해야 하므로 double 자료형을 사용해야 한다.
이때 각 스테이지별 인덱스를 알아야 하므로 pair를 사용하여 저장한다.

이제 스테이지를 실패율에 따라 정렬해야 한다. 우리는 문제에서 다음과 같은 정렬 조건을 추출해 두었다.

• 실패율의 내림차순으로 각 스테이지를 정렬한다.
• 만약 두 스테이지의 실패율이 같다면 인덱스가 작은 순으로 정렬한다.

이렇게 하면 기본적으로 실패율 내림차순으로, 실패율이 동일할 경우 인덱스 오름차순으로 정렬되며, 이를 answer에 차례대로 삽입하면 끝이다.

시행착오

스테이지에 도달한 사람이 하나도 없는 경우 실패율이 0이라는 정보를 누락하여 마무리에 약간 시간이 소요되었다. 정보를 잘 저장해두어야겠다.

소스 코드

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

using namespace std;

bool cmp(pair<int, double> p1, pair<int, double> p2){
    if(p1.second == p2.second){ // 실패율이 같은 경우
        return p1.first < p2.first; // 인덱스 오름차순대로 정렬
    }
    return p1.second > p2.second; // 실패율 내림차순으로 정렬
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<int, double> > v;
    double totaluser[N+1];
    double notclearuser[N+1];
    
    for(int i=0; i<=N; i++){
        totaluser[i] = notclearuser[i] = 0;
    } // 배열 초기화
    
    // stages는 1부터 n+1까지 존재
    // 실패율: 스테이지에 도달했으나 클리어 못한 수 / 스테이지에 도달한 전체 수
    for(int i=1; i<=N; i++){
        for(int j=0; j<stages.size(); j++){
            if(stages[j] >= i){
                totaluser[i]++; // 스테이지에 도달한 전체 수
                if(stages[j] == i){
                    notclearuser[i]++; // 스테이지에 도달했으나 클리어 못한 수
                }
            }
        }
    }
    for(int i=1; i<=N; i++){
        double a;
        if(totaluser[i] == 0) a = 0; // 스테이지에 도달한 유저가 없는경우 실패율 0
        else a = (notclearuser[i] / totaluser[i]); // 실패율 계산
        v.push_back(make_pair(i, a)); // "스테이지별 실패율" 삽입
    }
    
    sort(v.begin(), v.end(), cmp); // 규칙대로 정렬
    for(int i=0; i<v.size(); i++){
        answer.push_back(v[i].first);
    }    
    return answer;
}

교훈

• 실수 범위를 활용해야 할 때는 자료형을 double로 선언하는 것을 잊지 말자.
• 문제에서 필요한 정보를 빠짐없이 추출할 수 있도록 노력하자.