https://programmers.co.kr/learn/courses/30/lessons/42889
코딩테스트 연습 - 실패율 | 프로그래머스
실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를
programmers.co.kr
게임의 실패율을 구하고 실패율이 높은 스테이지 번호를 순서대로 출력하는 문제이다.
실패율이 같다면 스테이지 번호가 작은 순으로 출력한다.
실패율은 다음과 같은 식으로 구한다.
실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
| 5 | [2, 1, 2, 6, 2, 4, 3, 3] | [3,4,2,1,5] |
| 4 | [4,4,4,4,4] | [4,1,2,3] |
나는 먼저 주어지는 stages벡터를 정렬해주었다.
문제에서 주어진 첫 번째 예제(위의 표)를 예로 들어보면 stages를 정렬해줬을 때
1, 2, 2, 2, 3, 3, 4, 6 이 될 것이다.
그러면 스테이지 수만큼 for문을 돌면서 스테이지 번호와 현재 도전 중이 스테이지 번호가 같은 애들 사용자들에 대해서 순차적으로 처리해줄 수 있기 때문이다.
즉, i번째 스테이지 일 때, stages의 값이 i인 사용자들(해당 스테이지에 도전 중인 사용자, 클리어하지 못한 사용자)의 수를 스테이지에 도달한 플레이어 수로 나눠주면 된다. 그리고 현재 스테이지에 도전 중인 사용자들은 다음 스테이지에는 도달하지 못하므로 도전중인 사용자수에서 빼준다. 그리고 실패율을 해당 스테이지의 번호와 함께 벡터에 넣어준다.
여기서 실수할 수 있는 부분은 문제에서 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다라는 문제의 조건
을 잘 처리해주어야 한다. i번째 스테이지에 도전 중인 사용자나 클리어한 사용자가 모두 없다면 실패율은 0이 될 것이고 i번 이후의 스테이지들의 실패율도 모두 0이 될 것이다.
각 스테이지의 실패율을 모두 구했으면 정렬해주어야 한다.
실패율은 내림차순으로 그 실패율이 같다면 스테이지 번호를 오름차순으로 정렬해주기 위해서 비교 함수를 따로 구현(comp)하였다.
정렬이 끝났다면 정렬된 벡터의 두 번째 값(스테이지 번호)을 answer 벡터에 추가한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(const pair<double,int> &a, const pair<double, int> &b) {
//실패율 먼저 비교(내림차순)
if(a.first > b.first) {
return true;
} else if(a.first == b.first) {
//실패율이 같다면 스테이지 번호를 비교(오름차순)
if(a.second < b.second) {
return true;
} else {
return false;
}
} else {
return false;
}
}
vector<int> solution(int N, vector<int> stages) {
vector<int> answer;
vector<pair<double,int> > failrate;
sort(stages.begin(),stages.end());
//도전중인 사용자 수
int usernum = stages.size();
int index = 0;
for(int i=1; i<=N; i++) {
//i번째 스테이지에 도달한 유저가 없는 경우 실패율은 0
if(usernum == 0) {
failrate.push_back(make_pair(0, i));
continue;
}
int failcnt = 0;
//i번 stage에 도달했지만 클리어하지 못한 사용자수
while(stages[index] == i) {
failcnt += 1;
index++;
}
double rate = (double) failcnt/usernum;
failrate.push_back(make_pair(rate, i));
//i번째까지만 도달한 사용사들의 수를 빼준다.
usernum -= failcnt;
}
//문제 조건에 맞게 정렬(실패율 내림차순, 스테이지번호 오름차순)
sort(failrate.begin(),failrate.end(),comp);
//정답에 실패율이 높은 스테이지의 인덱스를 추가한다.
for(int i=0; i<N; i++) {
answer.push_back(failrate[i].second);
}
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 다트 게임 c++ (0) | 2019.08.28 |
|---|---|
| 프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 비밀지도 c++ (0) | 2019.08.26 |
| 프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0) | 2019.08.22 |
| 프로그래머스 탑 (c++) (0) | 2019.08.20 |
| 프로그래머스 프린터 (c++) (0) | 2019.08.20 |