프로그래머스 - 실패율

풀이

• stages의 각 원소: N (1 ~ 500 스테이지)
• stages의 길이: 사용자 수 (totalPlayer)

1. i는 1부터 N + 1까지 수를 돌면서 stages의 원소 중에서 i와 같은 수의 스테이지에 있는 사용자 수 unClearPlayer 구하기
2. 실패율 구하기 - unClearPlayer / totalPlayer
3. totalPlayer에서 unClearPlayer만큼 빼서 다음 스테이지에 도전한 사용자 수 구하기
4. 실패율을 내림차순으로 정렬하고 키 값을 answer에 저장

오답 01 (에러)

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    map<int, float, greater<int>> dict;
    int totalPlayer = stages.size();
    
    for (int i = 1; i <= N + 1; i++) // O(N)
    {
        int unClearPlayer = 0;
        
        for (int stage : stages) // O(N)
        {
            if (stage == i) 
                unClearPlayer++;
        }
        
        dict[i] = unClearPlayer / totalPlayer; // i번째 스테이지의 실패율 저장
        
        totalPlayer -= unClearPlayer;
    } // O(N^2)
    
    for (const auto& pair : dict)
    {
        answer.push_back(pair.first);
    }
    
    return answer;
}

에러 발생

signal: floating point exception (core dumped)

원인

0으로 나누려고 했기 때문

문제점

• int끼리 나누기 연산자를 하면 소수점을 제외한 몫이 도출됨 소수점을 포함한 계산 결과를 얻으려면 피연산자 둘 중 하나는 float나 double이어야 함
  
• greater<int>는 key를 내림차순 하는 것이기 때문에 값을 기준으로 내림차순 정렬 하려고 했던 의도와는 다르게 동작함

---

오답 02 (63 / 100)

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

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    // stages의 각 원소는 N (1 ~ 500 스테이지)
    // stages의 길이는 사용자의 수를 나타냄 - totalPlayer
    
    // i는 1부터 N + 1까지 수를 돌면서 stages의 원소 중에서 i와 같은 수의 스테이지에 있는 사용자 수 unClearPlayer 구하기
    // 실패율은 unClearPlayer / totalPlayer
    // totalPlayer에서 unClearPlayer만큼 빼서 다음 스테이지에 도전한 사용자 수 구하기
    
    // 값(실패율)을 기준으로 내림차순으로 정렬한 후, 정렬된 키 값을 answer에 저장
    
    vector<pair<int, float>> stagesFailRate;
    int totalPlayer = stages.size();
    
    for (int i = 1; i <= N; i++) // O(N)
    {
        float unClearPlayer = 0.0f;
        
        for (int stage : stages) // O(N)
        {
            if (stage == i) 
                unClearPlayer++;
        }
        
        if (totalPlayer == 0)
            stagesFailRate.push_back({i, 0.0f});
        else
            stagesFailRate.push_back({i, unClearPlayer / totalPlayer}); // i번째 스테이지의 실패율 저장
        
        totalPlayer -= unClearPlayer;
    } // O(N^2)
    
    sort(stagesFailRate.begin(), stagesFailRate.end(),
            [](pair<int, float>& a, pair<int, float>& b)
            { return a.second > b.second;}
        );

    for (auto pair : stagesFailRate)
    {
        answer.push_back(pair.first);
    }
    
    return answer;
}

문제점
정렬할 때 실패율이 같을 경우 예외 처리를 안 해서 순서가 보장되지 않음

sort 함수

sort(시작반복자, 끝반복자, 비교함수);

• 시작 반복자
  : 정렬을 시작할 위치 (ex. vector.begin())
• 끝 반복자
  : 정렬을 끝낼 위치 (ex. vector.end())
• 비교 함수(optional)
  : 정렬 기준을 지정하는 함수 (기본값 - 오름차순)

람다 함수 []

기본 문법

[](매개변수) { 함수 내용 }

sort 함수에 적용

pair<int, float>의 float를 기준으로 내림차순 정렬

sort(vector.begin(), vector.end(),
			[](pair<int, float>& a, pair<int, float>& b)
			{
					return a.second > b.second;
			});

---

정답 코드

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

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    // stages의 각 원소는 N (1 ~ 500 스테이지)
    // stages의 길이는 사용자의 수를 나타냄 - totalPlayer
    
    // i는 1부터 N + 1까지 수를 돌면서 stages의 원소 중에서 i와 같은 수의 스테이지에 있는 사용자 수 unClearPlayer 구하기
    // 실패율은 unClearPlayer / totalPlayer
    // totalPlayer에서 unClearPlayer만큼 빼서 다음 스테이지에 도전한 사용자 수 구하기
    
    // 값(실패율)을 기준으로 내림차순으로 정렬한 후, 정렬된 키 값을 answer에 저장
    
    vector<pair<int, float>> stagesFailRate;
    int totalPlayer = stages.size();
    
    for (int i = 1; i <= N; i++) // O(N)
    {
        float unClearPlayer = 0.0f;
        
        for (int stage : stages) // O(N)
        {
            if (stage == i) 
                unClearPlayer++;
        }
        
        if (totalPlayer == 0)
            stagesFailRate.push_back({i, 0.0f});
        else
            stagesFailRate.push_back({i, unClearPlayer / totalPlayer}); // i번째 스테이지의 실패율 저장
        
        totalPlayer -= unClearPlayer;
    } // O(N^2)
    
    sort(stagesFailRate.begin(), stagesFailRate.end(),
            [](pair<int, float>& a, pair<int, float>& b) {
                if (a.second == b.second) // 실패율이 같을 경우 번호가 작은 순서대로 정렬
                    return a.first < b.first;
                return a.second > b.second;
            }
        );

    for (auto pair : stagesFailRate)
    {
        answer.push_back(pair.first);
    }
    
    return answer;
}

---

교재 코드

// 1. 문제에서 요구하는 조건대로 실패율을 정렬하는 함수
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; // 2. 최종 답
    vector<float> challenger(N + 2, 0.0); // 3. 각 스테이지에 도달한 적이 있는 도전자의 수
    vector<float> fail(N + 2, 0.0); // 4. 특정 스테이지에 실패한 도전자의 수

    // 5. 각 스테이지의 인원을 기준으로 특정 스테이지에서
    //    실패한 인원수와, 각 스테이지에 도전한 적이 있는 인원수를 구함
    for (int i = 0; i < stages.size(); i++) {
        for (int j = 1; j <= stages[i]; j++)
            challenger[j]++;
        
        fail[stages[i]]++;
    }

    // 6. failRatio: 실패율을 저장 - first: stage 정보, second: 실패율
    vector<pair<int, float>> failRatio(N);

    // 7. 스테이지 정보 및 실패율을 저장
    for (int i = 0; i < N; i++) {
        failRatio[i].first = i + 1;

        if (challenger[i + 1] == 0)
            failRatio[i].second = 0;
        else
            failRatio[i].second = fail[i + 1] / challenger[i + 1];
    }

    // 8. 계산한 실패율을 문제에서 제시한 조건에 맞게 정렬
    sort(failRatio.begin(), failRatio.end(), compare);

    // 9. 최종 답을 반환하기 위해 실패율을 저장
    for (int i = 0; i < N; i++) {
        answer.push_back(failRatio[i].first);
    }
    
    return answer;
}

• stages[i]: 사용자가 도전 중인 스테이지

두 번째 for문
stages[i]의 사용자가 지나온 스테이지만큼 challengers[1]부터 chellengers[stages[i]]까지 1씩 증가시켜
도전자 수를 차근차근 증가시켜 구함

ex. stages[1]이 3일 때, challengers[1]부터 challengers[3]까지 각각 1씩 증가
stages[2]이 4일 때, challengers[1]부터 challengers[4]까지 각각 1씩 증가
=> challengers[1] ~ challengers[3]은 각각 2, challengers[4]는 1이 됨

첫 번째 for문
stages를 돌며 각 사용자가 실패한 스테이지 번호에 1씩 증가시켜 실패자 수를 구함