[Programmers] 실패율

문제 내용

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

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int N, vector<int> stages) {

    vector<int>answer;
    multimap<double, int, greater<double>> m1; //multimap 내림차순 정렬
    sort(stages.begin(), stages.end());

    int all = stages.size();
    int idx = 0;

    for (int i = 1; i < N+1; i++) {
        int elem = 0;
        while(idx < stages.size() && stages[idx] == i){
            idx++;
            elem++;
        }
        //key: 실패율, value: 스테이지
        m1.insert(make_pair((double)elem / (double)all, i)); 
        all -= elem;
    }

    for (auto it = m1.begin(); it != m1.end(); it++)
        answer.push_back(it->second);

    return answer;
}

풀이

생각한 로직은

1. 스테이지는 1부터 차례대로 존재하니까 스테이지 배열을 정렬하고, 각 스테이지의 실패율을 구한다.

2. 이때 만약 1 스테이지의 실패율을 구했으면 2로 넘어갈때 1 스테이지에 존재하는 사람들은 통계에 들어가지 않으므로 all에서 빼준다.

3. 스테이지의 실패율은 multimap에 저장하고 key는 실패율, value는 스테이지를 저장한다.(실패율이 같을 수 있기에 multimap을 사용하였다(key의 중복허용))

4. map의 특성상 key값을 기준으로 오름차순 정렬이 될테니, 요소의 가장 뒤부터 value를 가져온다. (우리가 원하는건 실패율이 큰값부터 출력이기에)
   
   

이렇게 생각하였다.

하지만 문제는 4번이었는데, 문제의 예제 1번을 기준으로, 3스테이지와 4스테이지의 실패율이 같기에 map에서는 value로 오름차순을 하게 되는데 이러면 3->4의 순서로 저장된다는 것이다.

그러니 내가 원하는 map의 value들은 5,1,2,4,3 이기를 원했는데
key값이 같을경우 value로 정렬하기에 5,1,2,3,4 로 저장된다는 것이다.

실패율이 같을경우 숫자가 작은 스테이지부터 출력해야하기에 위처럼 정렬된다면 뒤에서 부터 접근해도 정답을 낼 수 없었다.
나의 정답 : 4,3,2,1,5
원하는 정답 : 3,4,2,1,5

두번째로 생각한것은 max_element()로 실패율이 가장 높은값부터 추출하고 삭제할까 했었는데, 이도 3이 추출되는것이 아닌 4가 추출되었기에 답을 낼 수 없었다. (이도 아마 key를 기준으로 찾고 value로 판단한 거 같다.)

해결

최종적으로 해결한 방안은 map을 오름차순이 아닌, 내림차순으로 정렬하도록 바꾸었다. 이때 greater<>를 알게 되었다.

내림차순으로 바꿀 경우 실패율이 같아도 작은 스테이지가 먼저 나타나기에 정답을 내기 수월했다. 또한 실패율을 기준으로 큰값을 앞쪽에 배치하기에, 앞에서부터 접근하면 답을 낼 수 있었다.