실패율

풀이

실패율이 큰 stage 순서대로 출력하는 문제이다.

실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

1. 우선 각각 스테이지 별로 해당 스테이지에 머물러 있는 유저 수(==도달했으나 아직 클리어하지 못한 유저)와 해당 스테이지에 도달한 총 유저의 수를 구한다.
2. 구한 값을 나누어 실패율을 구한다. (스테이지에 도달한 유저가 없을 경우 실패율은 0)
3. 소팅하여 stage 번호를 answer에 담는다.

 

코드

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;
    }
}

 

🤦‍♀️ 메모

• 누적 스테이지 도달한 유저 수를 구하는 데에서 많이 헷갈렸다. 뒤로 갈수록 도달한 유저 수가 적어지는 것이므로, 뒤에서부터 누적해서 더하면 해당 스테이지에 몇 명의 유저가 도달했는지 알 수 있다!
• 그리고 소팅해서 소팅한 값을 출력하는게 아니라 해당 스테이지의 단계를 출력해야하기 때문에 따로 class를 만들어서 처리했다. class 만들기 귀찮아서 안만들고 해보려고 했는데 저게 가장 깔끔한듯