[프로그래머스/알고리즘]실패율

실패율

해결 방법

각 단계마다 스테이지에 도달했으나 아직 클리어하지 못한 플레이어수

각 단계마다 스테이지에 도달한 플레이어 수를 다 구해줘야 합니다.

N단계까지를 index 2개를 만들어줍니다(pass, notpass)

stage벡터에 한개씩 데이터를 읽는데 3단계에서 멈춘사람은 notpass배열 3번째 인덱스를 증가시켜주고  pass배열에 1~3를 증가시켜줘야합니다.

이렇게 다 돌면

각 단계마다 실패율을 구할 수 있고 인덱스와 실패율을 저장한 구조체를 정렬해서 결과값을 받아오면 됩니다.

소스 코드

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

struct Result {
	int number;
	double fail;
};

bool pred(Result a, Result b) {
	return a.fail < b.fail;
}
vector<int> solution(int N, vector<int> stages) {
	vector<int> answer;
	vector<Result> result;
	vector<int> notpass(N);
	vector<int> pass(N);
	
	for (int i = 0; i < stages.size(); i++) {
		if (stages[i] > N) {
			for (int j = 0; j < N; j++)
				pass[j]++;
		}
		else {
			for (int j = 0; j < stages[i]; j++) {
				pass[j]++;
			}

			notpass[stages[i] - 1]++;
		}		
	}

	for (int i = 0; i < pass.size(); i++) {
		result.push_back({ i + 1,(double)pass[i] / notpass[i] });
	}

	stable_sort(result.begin(), result.end(), pred);
	for (int i = 0; i < pass.size(); i++) {
		answer.push_back(result[i].number);
	}
	return answer;
}