Programmers 문제 42889번 실패율(2019 KAKAO BLIND RECRUITMENT문제)

해당 문제는 Programmers의 2019 KAKAO BLIND RECRUITMENT 출제 문제 중 하나입니다. 

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

코딩테스트 연습 - 실패율

Programmers 42889번 문제 실패율

---

해당 문제를 이해하는 과정은 크게 어려움이 없었습니다. 하지만 문제를 구현하는 과정에서 발목을 붙잡는 문제였습니다.

1. stages의 전체 사이즈를 cnt로 설정
2. stages에 표시되는 멈춰있는 스테이지를 갯수별로 보기 위해서 arr 배열에 저장
3. 실패율($\frac{스테이지에\,도달했으나\,아직\,클리어하지\,못한\,플레이어의\,수}{스테이지에\,도달한\,플레이어\,수}$) 계산: $\frac{arr[i]}{cnt}$
4. 실패율의 크기순으로 정렬, 실패율이 같은 경우 stage가 낮은 순서대로 정렬
5. 정렬된 key값(stages)을 answer에 저장

위와 같이 구현하였습니다. 이렇게 구현했을 경우 기본으로 제공해주는 테스트케이스는 문제없이 통과하였지만, 제출을 위해 채점해본 결과 70%의 정답률로 밖에 구현할 수 없었습니다. 그래서 발견한 부분은 다음과 같은 부분입니다. 

입력값 〉  5, [4, 4, 4, 4, 4]
기댓값 〉  [4, 1, 2, 3, 5]

stage 5는 존재하지만 4에서 모두 막힌 경우 5번째 stage는 아무도 도달하지 못했기에 실패율은 0이어야하지만 0으로 나눌 수 없었기에 그저 조건문 하나로 넘어버렸던 부분입니다. 해당 부분을 수정하였더니 문제없이 통과할 수 있었습니다.

---

코드는 다음과 같습니다:

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

using namespace std;

bool compare(pair<int, double> a, pair<int, double> b){
    if(a.second == b.second)
        return a.first < b.first ;
    return a.second > b.second ;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int arr[502] = {0, }, cnt = stages.size() ;
    vector<pair<int, double>> failure_rate ;
    
    for(vector<int>::iterator iter = stages.begin() ; iter != stages.end() ; iter++)
        arr[*iter] += 1 ;
        
    for(int i = 1 ; i < N+1 ; i++){
        if(cnt == 0)
            failure_rate.push_back(make_pair(i, 0.0)) ;
        else{
            failure_rate.push_back(make_pair(i, (double)arr[i]/cnt)) ;
            cnt -= arr[i] ;
        }
    }
    sort(failure_rate.begin(), failure_rate.end(), compare) ;
    
    for(int i = 0 ; i < N ; i++)
        answer.push_back(failure_rate[i].first) ;
    return answer;
}

---

해당 부분은 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/Programmers/P42889_Failure_Rate.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.