[프로그래머스/ 2019 KAKAO BLIND RECRUITMENT] 실패율

Q. 실패율

A.

class Solution {
    public int[] solution(int N, int[] stages) {
        // 전체 플레이어 수 저장
        int players = stages.length;
        
        // countStage[]: 1부터 N까지 각 스테이지에 도달한 플레이어 수 저장
        // 인덱스 N+1: 모든 스테이지를 클리어한 플레이어
        // 인덱스 1부터 N+1까지 사용하므로 배열 크기는 N+2가 되야함
        int[] countStage = new int[N + 2];
        
        // 각 플레이어가 현재 도전 중인 스테이지 번호를 이용해 스테이지 번호가 N이하인 경우만 카운팅
        // N+1은 모든 스테이지를 클리어한 경우이므로 실패율 계산에서 제외
        for (int stage : stages) {
            if (stage <= N) {
                countStage[stage]++;
            }
        }
        
        // fail[]: 1부터 N까지 각 스테이지의 실패율을 저장
        // 실패율 = 해당 스테이지에서 머문 플레이어 수 / 해당 스테이지에 도달한 플레이어 수
        double[] fail = new double[N + 1];
        int remain = players;
        
        // 스테이지 1부터 N까지 돌면서 실패율 계산
        // 만약 현재 스테이지에 도달한 플레이어가 있다면 실패율 계산, 도달한 플레이어가 없으면 실패율 0으로 정의
        for (int i = 1; i <= N; i++) {
            if (remain > 0) {
                fail[i] = (double) countStage[i] / remain;
            } else {
                fail[i] = 0;
            }
            // 다음 스테이지로 넘어가기 위해 현재 스테이지에 머무른 플레이어 수 빼주기
            remain -= countStage[i];
        }
        
        // answer: 스테이지 번호를 실패율 기준으로 정렬하여 결과 배열 구함
        // stagesNum: 1부터 N까지 스테이지 번호 저장
        int[] answer = new int[N];
        int[] stagesNum = new int[N];
        
        for (int i = 0; i < N; i++) {
            stagesNum[i] = i + 1;
        }
        
        // 선택 정렬 사용해 stagesNum 배열 정렬
        // 1. 실패율(fail)이 높은 스테이지가 먼저 오도록 정렬
        // 2. 실패율이 같으면, 스테이지 번호가 작은 것이 먼저 오도록 정렬
        for (int i = 0; i < N; i++) {
            int max = i;
            for (int j = i + 1; j < N; j++) {
                if (fail[stagesNum[j]] > fail[stagesNum[max]]) {
                    max = j;
                }
                else if (fail[stagesNum[j]] == fail[stagesNum[max]] && stagesNum[j] < stagesNum[max]) {
                    max = j;
                }
            }
            
            // i번째와 max번째 스테이지 번호 교환
            // 교환 후 i번째 위치의 스테이지 번호를 결과 배열에 저장
            int a = stagesNum[i];
            stagesNum[i] = stagesNum[max];
            stagesNum[max] = a;
            answer[i] = stagesNum[i];
        }
        
        return answer;
    }
}