프로그래머스>코딩테스트 연습>2019 KAKAO BLIND RECRUITMENT>실패율 - https://programmers.co.kr/learn/courses/30/lessons/42889
실패율이 큰 stage 순서대로 출력하는 문제이다.
실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
해당 스테이지에 머물러 있는 유저 수(==도달했으나 아직 클리어하지 못한 유저)
와 해당 스테이지에 도달한 총 유저의 수
를 구한다.import java.util.ArrayList;
import java.util.Collections;
class Solution {
static class Rate{
int idx; // stage number
double rate; // fail rate
public Rate(int idx, double rate) {
this.idx = idx;
this.rate = rate;
}
}
public static int[] solution(int N, int[] stages) {
int[] user_cnt = new int[N + 2]; // 각 stage에 머물러있는 user 수
int[] user_total_cnt = new int[N + 1]; // 각 stage에 도달한 전체 user 수
for (int i = 0; i < stages.length; i++) {
user_cnt[stages[i]]++;
}
// 스테이지에 도달한 유저 수 누적(?)하여 구하기
// 맨 마지막 stage는 n번째 + (n+1)번째
user_total_cnt[N] = user_cnt[N] + user_cnt[N + 1];
for (int i = N-1; i >= 1; i--) {
user_total_cnt[i] = user_cnt[i] + user_total_cnt[i + 1];
}
ArrayList<Rate> arr = new ArrayList<>(); // stage 번호와 실패율을 저장
for (int i = 1; i <= N; i++) {
if(user_total_cnt[i]==0){ //스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0
arr.add(new Rate(i, 0));
continue;
}
double rate = (double) user_cnt[i] / user_total_cnt[i];
arr.add(new Rate(i, rate));
}
// fail rate가 높은 순으로 sorting
Collections.sort(arr, ((o1, o2) -> Double.compare(o2.rate, o1.rate)));
// sorting 된 실패율의 stage 번호 저장
int[] answer = new int[N];
for (int i=0; i<arr.size(); i++) {
answer[i] = arr.get(i).idx;
}
return answer;
}
}
난이도 : LEVEL 2
누적 스테이지 도달한 유저 수를 구하는 데에서 많이 헷갈렸다. 뒤로 갈수록 도달한 유저 수가 적어지는 것이므로, 뒤에서부터 누적해서 더하면 해당 스테이지에 몇 명의 유저가 도달했는지 알 수 있다!
그리고 소팅해서 소팅한 값을 출력하는게 아니라 해당 스테이지의 단계를 출력해야하기 때문에 따로 class를 만들어서 처리했다. class 만들기 귀찮아서 안만들고 해보려고 했는데 저게 가장 깔끔한듯
딱히 없음