[C++] Programmers Lv. 1 "실패율"

🔵 문제 링크

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

프로그래머스

 

🔵 풀이

문제에서 제시한 대로 실패율을 구해 정렬하여 반환하는 문제이다.

제약 사항 중 하나는 stages의 길이가 최대 20만이므로, N^2의 시간복잡도로는 풀 수 없다.

 

💡Point

🔷 pair<>를 사용해 각 스테이지의 실패율을 효율적으로 저장하기

반환값으로 스테이지의 번호를 요구하는데, 실패율 데이터 또한 필요한 정보이므로 두 정보를 pair로 묶어 관리한다.

    vector<pair<int, double>> failureRate; // 실패율(스테이지 번호, 실패율)

 

🔷 누적차 개념을 이용하여 실패율 손쉽게 구하기

실패율은 다음과 같다.

해당 스테이지 실패자 수 / 해당 스테이지에 도달했거나 도달했던 사람 수

 

이때 "해당 스테이지에 도달했거나 도달했던 사람 수" 를 자세히 보자.

만약, 스테이지 1(첫 스테이지)의 실패율을 구한다고 가정할 때, 실패율은 다음과 같다.

스테이지 1 실패자 수 / 전체 플레이어 인원 (스테이지 1은 모두가 플레이 했으므로)

 

이어서 스테이지 2의 실패율을 구한다고 가정하면 실패율은 다음과 같다.

스테이지 2 실패자 수 / (전체 플레이어 인원 - 스테이지 1 실패자 수)

 

이처럼 각 스테이지에서의 실패자 수를 미리 구하고, 실패율을 계산할 때 이를 전체 플레이어 수에서 차감하는 식으로 구현하였다.

// 1번 스테이지부터 실패율 계산
    for(int i = 1; i <= N; i++)
    {
        // 남은 인원이 0이면 스테이지에 도달한 유저가 없다.
        if(total == 0)
        {
            failureRate.push_back({i, 0});
        }
        else
        {
            // 실패율 계산
            // 실패한 유저 수 / 남은 인원
            double rate = (double)fail[i] / total;
            failureRate.push_back({i, rate});
            
            // 스테이지의 실패율을 구한 후
            // 현재 스테이지에서 멈춰 있는 인원을 전체 인원에서 제외
            total -= fail[i];
        }
    }

 

🔷 정렬에 필요한 compare 함수를 제약 사항에 맞게 직접 구현하기

문제의 조건에서 알 수 있듯이 실패율이 높은 순대로, 또한 실패율이 같으면 스테이지의 번호가 작은 순대로 정렬해야 한다

    // 실패율 기준 내림차순, 실패율이 같으면 스테이지 번호가 작은 순으로 정렬
    sort(failureRate.begin(), failureRate.end(), [](auto &a, auto &b)
    {
        if(a.second == b.second)
            return a.first < b.first;
        return a.second > b.second;
    });

 

🔵 전체 코드

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

using namespace std;

vector<int> solution(int N, vector<int> stages) 
{
    vector<int> fail(N + 1, 0); // 각 스테이지 도전 실패자 수
    vector<pair<int, double>> failureRate; // 실패율(스테이지 번호, 실패율)
    
    // 각 스테이지 인덱스에 해당하는 실패자 수 계산
    for(int stage : stages)
    {
        // 원소값 N+1은 모든 스테이지를 클리어한 유저이므로
        // 실패자 수에 포함시킬 필요 없다. 
        if(stage <= N)
            fail[stage]++;
    }
    
    // 전체 플레이어 인원
    int total = stages.size();
    
    // 1번 스테이지부터 실패율 계산
    for(int i = 1; i <= N; i++)
    {
        // 남은 인원이 0이면 스테이지에 도달한 유저가 없다.
        if(total == 0)
        {
            failureRate.push_back({i, 0});
        }
        else
        {
            // 실패율 계산
            // 실패한 유저 수 / 남은 인원
            double rate = (double)fail[i] / total;
            failureRate.push_back({i, rate});
            
            // 스테이지의 실패율을 구한 후
            // 현재 스테이지에서 멈춰 있는 인원을 전체 인원에서 제외
            total -= fail[i];
        }
    }
    
    // 실패율 기준 내림차순, 실패율이 같으면 스테이지 번호가 작은 순으로 정렬
    sort(failureRate.begin(), failureRate.end(), [](auto &a, auto &b)
    {
        if(a.second == b.second)
            return a.first < b.first;
        return a.second > b.second;
    });
    
    vector<int> answer;
    for(auto &p : failureRate)
        answer.push_back(p.first);
    
    return answer;
}

 

🔵 시간 복잡도

• M = stages.size() (최대 20만)
• N = 스테이지 개수 (최대 500)

전체 시간 복잡도는

실패자 수 계산 O(M) +실패율 계산 O(N) + 정렬 O(NlogN) + 결과 벡터 채우기 O(N) 이므로,

O(M + NlogN)이다.