[2019 카카오 신입 공채 1차 코딩테스트] 2. 실패율

문제 정보와 자세하고 정확한 풀이는 요기로 ~~~ -> http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

 

개인적으론 1번 문제보다 더 간단했던 것 같다!

풀어야 하는 흐름은 stages의 정보를 입력받으면서 각 stage를 해결한 명수, 해결하지 못한 명수를 체크하고, 그 결과를 바탕으로 실패율을 구한다음 정렬하면 된다!

정렬할때 실패율은 높은 순으로, 실패율이 같다면 스테이지가 낮은 순으로 정렬해야한다!

 

1. stages를 쭉 읽는다. 읽어온 값을 i라고 하면 i-1까지는 해결한 문제이므로 clear[i]++, i번째 stage는 해결하지 못한 단계이므로 fail[i]++을 한다. 

2. 이제 1부터 N까지 돌면서 실패율을 구한다. 이 때 도달한 유저가 없어서 clear와 fail모두 0인 경우가 존재해 0으로 나누는 예외가 발생하지 않도록 미리 처리해준다.

3. 구해놓은 실패율을 이제 vector에 push 해야한다. C++ stl의 sort 함수는 first원소를 기준으로 정렬한 후, first에서 같은 값이 있다면 second를 기준으로 정렬한다. 우리는 first는 내림차순, second는 오름차순이 되야하므로, 꼼수를 약간 쓸것이다. first는 실패율을 넣고, second에는 stage를 넣는데, 대신에 stage는 -1을 곱해서 넣는다. (더 작은 스테이지가 뒤로갈 수 있도록 하기 위함이다)

4. vector를 거꾸로 읽어가면 된다! 단, 스테이지에 다시 -1곱하는것을 잊지말기. 실패율은 높은 순서대로, 스테이지는 낮은 순서대로 꺼낼 수 있다!

 

소스코드 보기 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
int clear[505];
int fail[505];
using namespace std;
 
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    for (int i = 0; i < 505; i++)
    {
        clear[i] = 0;
        fail[i] = 0;
    }
    //initialize for testcase
    for (int i = 0; i < stages.size(); i++)
    {
        for (int j = 0; j < stages[i]; j++)
            clear[j]++;
        fail[stages[i]]++;
    }
 
    vector<pair<float, int> > v;
    for (int i = 1; i <= N; i++)
    {
        float rate = 0;
        if((clear[i]+fail[i]) != 0)
            rate = (float)fail[i] / (clear[i] + fail[i]);
        v.push_back({ rate, -i });
        //cout << rate << endl;
    }
    sort(v.begin(), v.end());
    for (int i = v.size()-1; i >=0; i--)
    {
        answer.push_back(-1 * v[i].second);
    }
    return answer;
}