[프로그래머스] 실패율 C++ 풀이

https://programmers.co.kr/learn/courses/30/lessons/42889?language=cpp 

코딩테스트 연습 - 실패율

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double, int>> v;
    int cur[502];
    int dodal[502];
    fill(cur, cur+N+1, 0);
    fill(dodal, dodal+N+1,0);
    
    for (int i = 0; i < stages.size(); i++)
    {
        cur[stages[i]]++;
        for (int j = 1; j <= stages[i]; j++)
        {
            dodal[j]++;
        }
    }

    for (int i = 1; i <= N; i++)
    {
        if(dodal[i]==0)
            v.push_back(make_pair(0, i));
        else
            v.push_back(make_pair((double)cur[i] / dodal[i], i));
    }
    sort(v.begin(), v.end(), comp);

    for (int i = 0; i < v.size(); i++)
        answer.push_back(v[i].second);

    return answer;
}

 

변수

vector<pair<double, int>> v;
int cur[502];
int dodal[502];

v : (실패율, 스테이지)가 담길 것

cur : i 스테이지에서의 유저의 수 ( 어떤 스테이지에 도달했으나 아직 클리어하지 못한 플레이어들 )

dodal : i 스테이지에 도달한 유저의 수

 

fill

fill(cur, cur+N+1, 0);
fill(dodal, dodal+N+1,0);

fill로 초기화할 때 왜 cur+N이 아닌 cur+N+1이냐면 

stages에는 1이상 N+1 이하의 자연수가 담겨 있으므로

cur+N+1까지 0으로 초기화시켜준 것이다.

 

for (int i = 0; i < stages.size(); i++)
{
	cur[stages[i]]++;
	for (int j = 1; j <= stages[i]; j++)
	{
		dodal[j]++;
	}
}

cur에는 유저가 도달한 위치를 표시를 할 것이다.

그러므로 stages[i]번째에 있는 스테이지 정보를 이용해 cur에 +1을 해주어 해당 위치에 유저가 한 명 있다고 추가해준다.

dodal에는 stages[i]를 통해 이 유저가 지나온 스테이지들을 +1 해주어 스테이지에 도달한 플레이어라는 것을 남겨준다.

 

 

    for (int i = 1; i <= N; i++)
    {
        if(dodal[i]==0)
            v.push_back(make_pair(0, i));
        else
            v.push_back(make_pair((double)cur[i] / dodal[i], i));
    }

if(dodal[i])는 문제의 조건에 따라

스테이지에 도달한 유저가 없는 경우 실패율을 0으로 정의함이다.

그런 게 아니라면 실패율과 스테이지를 계산하여 넣어준다.

 

sort(v.begin(), v.end(), comp);

for (int i = 0; i < v.size(); i++)
	answer.push_back(v[i].second);

문제의 내용대로 정렬 기준을 만들어 정렬합니다.

그리고 순서대로 스테이지를 answer에 넣어줍니다.