[2019 카카오 블라인드 채용 코딩테스트] 실패율 C++ 풀이 및 정답 코드

문제 링크

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

프로그래머스

 

 

 

문제 설명

나머지 문제 중에서 가장 쉬운 문제로, 실제 코딩테스트가 이루어졌을 때의 정답률은 55.57%이다.

주어진 N개의 스테이지에 대해 실패율을 구하고 실패율에 따라 내림차순으로 정렬한 배열을 리턴하는 문제이다.
문제 설명이 모호하지만, 예시를 보면 스테이지 n의 실패율은 stages 중 n의 갯수 / stages 중 n 이상인 것의 갯수 이다.

 

 

 

문제 풀이

문제는 총 4단계 페이즈로 나눌 수 있다.

1. 분자 계산
일단은 실패율의 분자가 될 요소인 "각 스테이지마다 머물러 있는 유저들의 수"를 세야하므로, dp 배열을 사용해 수를 카운트했다.
첫 번째 카운트가 끝나면 dp[i] = 스테이지 i에 머무른 사람의 수이므로, dp[stage]++를 해주면 된다.
주의 할 점은 문제 조건 중 N+1이 존재하므로 dp 배열을 초기화할 때 사이즈에 유의해야한다.

2. 분모 계산
그 다음 실패율의 분모가 될 "stages 중 n 이상인 수"의 갯수를 세야하므로 dp 배열을 누적합한다.
주의할 점은 n 이하인 수가 아니라 이상인 수를 세어야하므로 역순으로 누적합해줘야한다.

3. 실패율 계산
그 다음은 구한 분자와 분모를 바탕으로 실패율을 계산해주면 된다.

4. 조건에 맞게 정렬
실패율까지 계산했으면 정렬을 할 차례다.
나는 rates 라는 vector<pair<int, double>>을 만들어 각각에 pair<스테이지, 실패율>을 저장했다.
정렬 메소드를 활용할 건데, 주의 할 점은 내가 pair의 second value를 기준으로 내림차순 정렬을 할 것이라는 것과, second value가 같으면 first value인 스테이지 넘버가 작은 순으로 정렬을 할 것이라는 점이다.
따라서 comparePair 함수를 정의해 sort 메소드의 세번째 인자로 넘긴다.

자세한 사항은 아래 코드를 참고하세요.

 

 

 

코드

주석 없는 코드

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

using namespace std;

bool comparePair(pair<int, double> &a, pair<int, double> &b) {
    return a.second > b.second || (a.second == b.second && a.first < b.first);
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> dp(N+2,0);
    vector<pair<int, double>> rates(N);
    
    // count
    for (auto stage : stages) {
        dp[stage]++;
    }
    
    // accumulate
    for (int i=N; i>0; i--) {
        int temp = dp[i];
        dp[i]+=dp[i+1];
        if (dp[i] == 0)
            rates[i-1] = make_pair(i-1, 0.0f);
        else
            rates[i-1] = make_pair(i-1, (double)temp/(double)dp[i]);
    }
    
    sort(rates.begin(), rates.end(), comparePair);
    
    for (auto rate : rates)
        answer.push_back(rate.first+1);
    
    return answer;
}

 

주석 있는 코드

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

using namespace std;

bool comparePair(pair<int, double> &a, pair<int, double> &b) {
    return a.second > b.second || (a.second == b.second && a.first < b.first);
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> dp(N+2,0);
    vector<pair<int, double>> rates(N);
    
    // 1번 분자 계산
    for (auto stage : stages) {
        dp[stage]++;
    }
    
    for (int i=N; i>0; i--) {
        int temp = dp[i];
        // 2번 분모 계산
        dp[i]+=dp[i+1];
        // 3번 실패율 계산
        if (dp[i] == 0)
            rates[i-1] = make_pair(i-1, 0.0f);
        else
            rates[i-1] = make_pair(i-1, (double)temp/(double)dp[i]);
    }
    
    4번 정렬
    sort(rates.begin(), rates.end(), comparePair);
    
    for (auto rate : rates)
        answer.push_back(rate.first+1);
    
    return answer;
}

 

 

 

 

시공간 복잡도

시간 복잡도: O(n*log n)

공간 복잡도: O(n)

 

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰

쉬웠다.