프로.카카오.실패율

 

• second값 기준 정렬

vector pair 의 second 값 기준 정렬을 하고 싶은데 [].second 형태를 어찌해야하나 몰랐다.

-> 인자로 pair<int, int>를 넘겨주면 된다!

 

애초에 각 인덱스에 접근해서 인자를 pair로 넘겨준거니까 pair로 받는 게 맞는 것.

bool compare(const pair<int, float>& a, const pair<int, float>& b)
{
    return a.second > b.second;
}

 

 

• 1번 케이스와 2번 케이스의 결과값 기준 다름

스테이지를 끝까지 클리어한 사람이 있는 경우와 아닌 경우가 갈리는데,

그 이유는 편의를 위해(sum계산) idx를 stage+1까지로 설정했고, 내림차순 정렬을 하며 값이 밀렸기 때문이다.

-> 0아닌 값 push.

 

예제는 맞는데 실패. 

아마 값이 밀려서 그런듯하다.

 

cleared[] 하나로 스테이지당 플레이어 수와 스테이지/실패율에 사용했기 때문으로 보인다.

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

using namespace std;

//전체 스테이지 수: N
//도달 스테이지: stages
// 실패율: 해당 스테이지 도달 / 해당 스테이지 이상 도달

//실패율 기준 내림차순 스테이지 출력
//실패율이 같다면 오름차순
//도달 우저가 없는 경우 실패율 0 -> 신경 x

bool compare(const pair<int, float>& a, const pair<int, float>& b)
{
    return a.second > b.second;
}

vector<int> solution(int N, vector<int> stages) {
    vector<pair<int, float>> cleared(N + 1, { 0,0.f });
    
    //cleared vector
    for (int i = 0; i < stages.size(); ++i)
        ++cleared[stages[i] - 1].second;

    for (int i = 0; i < N; ++i)
    {
        int sum = 0;

        for (int j = i; j <= N; ++j)
            sum += cleared[j].second;

        //first: stage, second: failureRate
        cleared[i].first = i + 1;

        //failureRate = arr[idx]/sum 
        cleared[i].second /= sum;
    }

    sort(cleared.begin(), cleared.end(), compare);

    vector<int> answer;

    for (int i = 0; i <= N; ++i) 
    {
        if (cleared[i].first)
            answer.push_back(cleared[i].first);
    }

    return answer;
}

 

 

• 개선

스테이지당 플레이어수와 스테이지/실패율 컨테이너를 분리했다.

compare에서 동점에 대한 처리를 해주었다.

bool compare(const pair<int, float>& a, const pair<int, float>& b)
{
    if (a.second > b.second)
        return true;
    else
        return a.first < b.first;
}


vector<int> solution(int N, vector<int> stages) {
    vector<int> stageCount(N + 1, 0);
    vector<pair<int, float>> failureRates(N, { 0,0.f });
    
    for (int stage : stages) {
        ++stageCount[stage - 1];
    }

    int users = stages.size();

    for (int i = 0; i < N; ++i)
    {
        //first: stage, second: failureRate
        failureRates[i].first = i + 1;
        failureRates[i].second = (double)stageCount[i] / users;
        users -= stageCount[i];
    }

    sort(failureRates.begin(), failureRates.end(), compare);

    vector<int> answer;
    for (const auto& failureRate : failureRates) {
        answer.push_back(failureRate.first);
    }

    return answer;
}

 

 

뭐가 문제인지 모르겠네.

자바는 혼자 풀었는데.. 이럴 땐 성장못한 느낌이라 의지가 줄어들지만, 그래도 해야한다.

 

비교함수 수정하면서 first넣음.

float인데 double로 형변환.

 

통과 코드

bool compare(const pair<int, float>& a, const pair<int, float>& b)
{
    if (a.second != b.second)
        return  a.second > b.second;
    else
        return a.first < b.first;
}


vector<int> solution(int N, vector<int> stages) {
    vector<int> stageCount(N + 1, 0); //idx 예외 방지
    vector<pair<int, float>> failureRates(N, { 0,0.f });

    //해당 스테이지 클리어한 플레이어 수
    for (int stage : stages) {
        ++stageCount[stage - 1];
    }

    int clearUsers = stages.size();

    for (int i = 0; i < N; ++i)
    {
        //first: stage, second: failureRate
        failureRates[i].first = i + 1;
        if (clearUsers > 0)
        {
            failureRates[i].second = (float)stageCount[i] / clearUsers;
            clearUsers -= stageCount[i];
        }
    }

    sort(failureRates.begin(), failureRates.end(), compare);

    vector<int> answer;
    for (const auto& failureRate : failureRates) {
        answer.push_back(failureRate.first);
    }

    return answer;
}