Lv1_[실패율, C++] 풀이 및 알고리즘 정리 - 프로그래머스

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

아래의 예시를 가지고 설명

- stages : [2, 1, 2, 6, 2, 4, 3, 3]

- N = 5

 

1. map<int, int> 초기화

 

2. map에 stages 넣기

stages : [2, 1, 2, 6, 2, 4, 3, 3]  (총 8명)

 

3. 실패율 계산 후 pair<int(스테이지), double(실패율)>에 저장

 

4. 계산 완료된 결과값 정렬

커스텀 정렬로 원하는 조건에 따른 정렬하도록 함수 구현

실패율이 높은 순으로 내림차순 정렬 (단, 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 앞으로; 오름차순)

 

#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
vector<int> solution(int N, vector<int> stages)
{
    vector<int> answer;
    map<int, int> m;
    
    // 1. map 초기화 
    for(int i = 1; i <= N; i++) {
        m[i] = 0;
    }
 
    // 2. 해당 스테이지에 머무르는 플레이어수 저장
    for(auto item : stages) {
        if(item <= N) {
            m[item]++;
        }
    }
 
    // 3. 실패율 계산 후 pair<int(스테이지), double(실패율)>에 저장
    int stages_size = stages.size();
    int accumulationCnt = 0;
    vector<pair<int, double>> stageFail_Per;    // <stage, Fail_Per>
    map<int, int>::iterator iter;
    for(iter = m.begin(); iter != m.end(); ++iter) {
        int key = iter->first;
        int value = iter->second;
        double remainingNum = static_cast<double>(stages_size - accumulationCnt);
 
        if(remainingNum != 0.0) {
            stageFail_Per.emplace_back(make_pair(key, value / remainingNum));
        } else {
            // 해당 스테이지에 아무도 도달하지 않음
            // 성공도 실패도 없으니 실패율 0
            stageFail_Per.emplace_back(make_pair(key, 0));
        }
 
        accumulationCnt += value;
    }
 
    // 4. 계산 완료된 결과값 정렬
    sort(stageFail_Per.begin(), stageFail_Per.end(),
            [](pair<int, double> a, pair<int, double> b) {
                if(a.second == b.second) {    // 실패율이 같으면 낮은 스테이지 반환 (내림차순 정렬)
                    return (a.first < b.first);
                } else {                    // 그렇지 않으면 실패율이 높은 값 반환 (오름차순 정렬)
                    return (a.second > b.second);
                }
            }
    );
 
    // 5. 결과값 반환
    for(auto item : stageFail_Per) {
        answer.emplace_back(item.first);
    }
 
    return answer;
}

결과 비교용

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓