[프로그래머스] Level 1. 실패율

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

프로그래머스

 

실패율 : 해당스테이지에 머무르고 있는 유저 수 / 해당 스테이지에 도달한 유저 수 이다.

 

중요한것은 실패율 계산이다. 1스테이지 도전중인 유저는 2스테이지에 도달하지 못했기 때문에 2스테이지 실패율에 영향을 주지 않는다. 즉,

2스테이지의 실패율 = stages 에서 2의 개수 / (stages 사이즈  - 2보다 적은 스테이지에 머무른 유저 수 )

 

분모부분과 분자부분을 따로 구한뒤 조합하는 방법을 생각했다.  fails_up 이 분모부분,fails_down 이 분자부분이다. 

1. 먼저 fails_up과 fails_down을 각각 구한다. fails_up은 단순히 해당 스테이지에 머무른 유저 수이고, fails_down은 유저 수에서 시작해서, 해당되지 않는 유저가 나올 때마다 - 시켜주는 구조이다.

2.  fails_up과  fails_down을 조합하여 실패율을 계산하고 , <스테이지번호, 실패율> 을 이루는 pair로 만들어 리스트에 담는다.

3. compare함수를 이용하여 sort() 함수를 호출한다. 실패율이 같을 경우 스테이지가 작은 순서대로 출력한다.

4. pairs에서 스테이지번호를 나타내는 first값만 추출하여 answer 리스트에 넣는다.

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

using namespace std;

bool compare(pair<int,float> a , pair<int, float>b);
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer(N);
    
    int user_cnt = stages.size();
    
    vector<int> fails_up(N+2, 0);
    vector<int> fails_down(N+2, stages.size());
    
    for(int i = 0; i< stages.size(); i++  ){
        int number = stages[i];
        fails_up[number] ++;
        for(int j= number+1; j<fails_down.size(); j++ ){
            fails_down[j] -= 1;
        }
    }
    
    vector<pair<int,float>> pairs(N);
    for(int i=0 ; i< N ; i++){
        pairs[i].first = i+1;
        if(fails_down[i+1]<=0) pairs[i].second = 0;
        else pairs[i].second = fails_up[i+1]/(float)fails_down[i+1];
        
        //cout <<  pairs[i].first << fails_up[i+1] << fails_down[i+1] <<endl;
    }
    
    sort(pairs.begin(), pairs.end(),compare);
    for(int i = 0; i<pairs.size(); i++){
        answer[i] = pairs[i].first;
    }
    return answer;
}

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

 

 

 

후기

분모, 분자로 나누어서 실패율을 계산하는 방법은 빨리 생각해냈는데, 

pair을 모르고있어서 map 을 사용하려고 시도했었다. sort() 부분이 정상적으로 수행되지 않아서 시간을 많이 잡아먹었다 ㅠㅠ  그래도 점점 c++ 에 익숙해지고 있는 것 같다. 해결방법이라도 생각해낸게 어디냐.>!