문제 풀이/문제 풀이(프로그래머스)
2019 KAKAO BLIND RECRUITMENT > 실패율
풀뿌리
2024. 11. 26. 11:19
문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/42889
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
배열을 순회하며 이를 pair를 컨테이너로 쓰는 vector 형태의 자료구조로 변환하여 풀었다.
먼저 stages에서 주어진 각 플레이어들의 최대 도달 레벨을 각 레벨의 시점으로 변경하는 자료구조를 만들었다.
이는 스테이지 순서대로 순회하기 위해 만든 구조이다.
이 자료구조를 순회하면 각 stage에 도달한 사람은 다음과 같다.
(전체 플레이어의 수) - (이전 단계들에서 탈락한 플레이어의 수)
따라서 total_user의 전체 플레이어의 수를 더해준 다음 각 레벨에서 실패율을 구하고 난 다음 해당 스테이지가 마지막 도전인 플레이어들의 수만큼 제외해 주었다.
이렇게 구한 실패율과 해당 레벨을 pair 구조에 넣은 다음 sort 해 주어 문제를 해결하였다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int N, vector<int> stages) {
vector<int> answer;
vector<int> level(N + 1, 0); // 스테이지별 도달한 사용자 수
vector<int> users(N + 1, 0); // 각 스테이지를 플레이한 사용자 수
vector<pair<double, int>> failureRates; // 실패율과 스테이지 번호를 저장
for (int stage : stages) {
if (stage <= N) {
level[stage]++;
}
}
int total_users = stages.size(); // 전체 사용자 수
for (int i = 1; i <= N; i++) {
if (total_users == 0) {
failureRates.push_back(make_pair(0.0, i)); // 남은 사용자가 없으면 실패율은 0
} else {
double failureRate = (double)level[i] / total_users; // 실패율 계산
failureRates.push_back(make_pair(failureRate, i));
total_users -= level[i]; // 해당 스테이지에 도달한 사용자를 제외한 나머지 사용자의 수로 갱신
}
}
sort(failureRates.begin(), failureRates.end(), [](pair<double, int> a, pair<double, int> b) {
if (a.first == b.first) return a.second < b.second;
return a.first > b.first;
});
// 정렬된 스테이지 번호를 정답에 추가
for (auto fr : failureRates) {
answer.push_back(fr.second);
}
return answer;
}