[2019 KAKAO BLIND RECRUITMENT] 실패율

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

코딩테스트 연습 - 실패율

hash table 에 < 스테이지, 실패율 > 을 insert 한 뒤, 실패율에 따라서 정렬하여 answer 에 적절한 값을 push 한다.

 

challenge 배열에는 각각의 스테이지에 대하여 도전을 했다면(거쳐왔다면) 하나씩 증가한다.

예를 들어, stage 배열이 [2, 1, 2, 6, 2, 4, 3, 3] 인 경우에는 challenge[1] = 8 (스테이지 1 은 8 명이 모두 지나갔으므로), challenge[2] = 7 (스테이지 2 는 7 명이 거쳐갔으므로) 이다.

 

num 배열에는 각각의 스테이지에 머물고 있는 사람의 개수를 저장한다.

예를 들어, stage 배열이 [2, 1, 2, 6, 2, 4, 3, 3] 인 경우에는 num[1] = 1, num[2] = 3 ... 이다.

 

그러면 실패율은 num[i]/challenge[i] 로 정의할 수 있는데 이때 주의해야할 점은 challenge[i] 가 0 일 수 있다는 것이다. 이에 대한 예외처리를 해주어야 하는 것에 주의하자.

 

위와 같이 실패율을 구하면, < 스테이지, 실패율 > 원소를 hash table 에 저장한다. 그리고 pair<int, double> 을 원소로 가지는 vector 인 temp 를 이용하여 hash table 을 정렬한다. 이때 람다 함수를 이용하여 comp 함수를 정의하는데, 실패율이 같다면 스테이지의 이름을 오름차순으로 정렬하고 실패율이 다르면 실패율에 따른 내림차순으로 정렬되도록 설정한다. 이후 정렬된 temp 배열의 원소 중 stage 에 해당하는 값을 answer 배열에 차곡차곡 저장하면 된다.

 

 

[C++]

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

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<int> challenge(N+1, 0);
    vector<int> num(N+1, 0);
    unordered_map<int, double> h_map;

    for (int i = 0; i < stages.size(); i++)
    {
        for (int j = stages[i]; j > 0; j--)
        {
            challenge[j]++;
        }
        num[stages[i]]++;
    }

    for (int i = 1; i <= N; i++)
    {
        h_map[i] = 0.0;
        if (challenge[i] != 0)
        {
            h_map[i] = (double)num[i] / (double)challenge[i];
        }
    }


    vector<pair<int, double>> temp(h_map.begin(), h_map.end());
    sort(temp.begin(), temp.end(), [](pair<int, double> a, pair<int, double> b)
        {
            if (a.second == b.second)
            {
                return a.first < b.first;
            }
            return a.second > b.second;
        });


    for (int i = 0; i < temp.size(); i++)
    {
        answer.push_back(temp[i].first);
    }
    return answer;
}