[2019 kakao blind recruitment] 02. 실패율(cpp/python)

실패율

프로그래머스

문제 설명

N개의 stage 에 대한 카운팅 정렬을 하고 stage에 대한 실패율
(스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수)
을 구하는 문제다.

문제 풀이

소스코드 : C++

1. 카운팅 정렬을 위한 cnt[501] 배열을 전역변수와 전체 사용자 수 size = stage.size()를 선언한다.
2. stages에 들어있는 값들을 카운팅 정렬한다. 이때 해당 값이 N+1인 값은 제외하고 정렬한다. (N+1은 모든 스테이지를 클리언 사용자)
3. 실패율을 구하기위한 vector<ID> ans를 선언한다. (ID = pair<int, doblue>)
4. stage 1부터 stage N 까지 카운팅 정렬한 값을 이용하여 실패율을 구한다.
   1. value/size를 이용하여 해당 stage와 실패율을 ans에 넣어준다.(value = stage i에 머문 사람)
   2. size -=value를 한다. 다음 stage 탐색시 size=0 이면 실패율을 0으로 넣어준다.
5. ans를 실패율이 큰 순서로 정렬하고 만약 실패율이 같다면 stage값이 낮은 순으로 정렬한다.
6. 정렬한 값으로 stage값들을 answer에 넣어준다.

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

using namespace std;

int cnt[501];
struct ID{
    int idx;
    double value;
};

bool comp(ID a, ID b){
    if(a.value == b.value)return a.idx < b.idx;
    return a.value > b.value;
}
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int size = stages.size();
    for(int i : stages)
        if(i!=N+1)cnt[i]++;

    vector<ID> ans;
    for(int i=1; i<=N; i++){
        int key = i;
        int value = cnt[i];
        if(size == 0)ans.push_back({key, 0});
        else ans.push_back({key,value/(double)size});
        size -= value;
    }

    sort(ans.begin(), ans.end(), comp);
    for(auto res : ans)
        answer.push_back(res.idx);
    return answer;
}

소스코드 : Python

C++ 로직과 비슷하지만 카운팅 정렬 부분을 딕셔너리를 이용하여 문제를 해결했다.

딕셔너리인 tmp 리스트는 stage size 만큼 할당되어있으므로 실패율 계산할 때 size==0이되면 break를 걸어준다.

def solution(N, stages):
    answer = []
    stages.sort()
    size = len(stages)
    tmp = {i : 0 for i in range(1,N+1)}
    for i in stages: 
        if i != N+1 : tmp[i] +=1
    for i in tmp.items():
        key = i[0]
        value = i[1]
        if size==0 : break
        tmp[key] = value/size
        size-=value    

    tmp = sorted(tmp, key=lambda k: tmp[k], reverse=True)
    answer = tmp
    return answer