💭 풀이

1. 스테이지에 도달한 플레이어 수
   1 ~ N번 스테이지까지 stages 배열 전체를 한 번 순회하며 현재 스테이지 번호와 같거나 크면 count를 1씩 증가

2. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수
   1 ~ N번 스테이지까지 stages 배열 전체를 한 번 순회하며 현재 스테이지 번호와 같으면 count를 1씩 증가

3. 실패율 구하기
   divided by zero 유의

4. 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호 배열 정렬

오답(63.0 / 100.0)

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

using namespace std;

bool compare(pair<int, float> a, pair<int, float> b) {    
    return a.second > b.second;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer(N, 0);
    vector<int> reachedPlayer(N, 0);
    vector<int> notClearPlayer(N, 0);
    vector<pair<int, float>> failRate(N, pair<int, float> (0, 0.0f));
    
    for (int i = 0; i < N; i++) {
        int currStage = i + 1;
        failRate[i].first = currStage; // 스테이지 번호
        
        for (int stageNum : stages) {
            if (currStage <= stageNum) {
                reachedPlayer[i]++;
            }
            
            if (currStage == stageNum) {
                notClearPlayer[i]++;
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        if (reachedPlayer[i] != 0) {
            failRate[i].second = (float)notClearPlayer[i] / (float)reachedPlayer[i];
        }
    }
    
    sort(failRate.begin(), failRate.end(), compare);

        for (int i = 0; i < N; i++) {
                answer[i] = failRate[i].first;
        }
    
    
    return answer;
}

💥 원인

• 실패율이 같은 경우 스테이지 번호가 작은 순서대로 오도록 예외처리 안 함

🤔 시도

• 그냥 a, b 실패율이 같을 때는 정렬 안 하고 b가 더 작을 때만 정렬되도록 하려고 했는데 이것도 실패함
• sort에서 a에 스테이지 번호가 더 작은 게 오고, b에 그 다음 스테이지 번호가 올 줄 알았는데 그 반대였음
• 즉, 3번과 4번 스테이지 실패율은 같지만 a가 4고 b가 3이니까 그대로 4, 3 순으로 정렬된 것
• sort()에서 compare(a, b) 호출 시, a와 b는 비교할 두 원소일 뿐, 순서는 introsort 정렬 알고리즘에 따라 달라지며, 항상 순차적으로 오지 않음
• 즉, a와 b에 각각 3번과 4번 스테이지가 오는 게 아니기 때문에 따로 명확히 예외 처리를 해야함

정답

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

using namespace std;

bool compare(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> answer(N, 0);
    vector<int> reachedPlayer(N, 0);
    vector<int> notClearPlayer(N, 0);
    vector<pair<int, float>> failRate(N, pair<int, float> (0, 0.0f));
    
    for (int i = 0; i < N; i++) {
        int currStage = i + 1;
        failRate[i].first = currStage; // 스테이지 번호
        
        for (int stageNum : stages) {
            if (currStage <= stageNum) {
                reachedPlayer[i]++;
            }
            
            if (currStage == stageNum) {
                notClearPlayer[i]++;
            }
        }
        
        if (reachedPlayer[i] != 0) {
            failRate[i].second = (float)notClearPlayer[i] / (float)reachedPlayer[i];
        }
    }
    
    sort(failRate.begin(), failRate.end(), compare);

	for (int i = 0; i < N; i++) {
		answer[i] = failRate[i].first;
	}
    
    return answer;
}