[JAVA] 프로그래머스 : 실패율

https://school.programmers.co.kr/learn/courses/30/lessons/42889
이 문제를 풀기 위해여 hashmap도 사용해 보았다.. 하지만 정렬에서 어려움을 맞아 다시 구현하였다.

N번째 스테이지에서 그 다음 스테이지를 도전하는 사람도 있을 수 있으니 초기 배열을 N+1로 설정 해 주어야 하는데, 이 케이스를 생각하지 못해 시간이 정말 많이 소요되었다.

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int length = stages.length; // 전체 도전자 수
        int[] arr = new int[N + 1]; // 다음 스테이지에 도전하는 경우도 따져 주어야 함

        for (int i = 0; i < length; i++) {
            if (stages[i] <= N) {
                arr[stages[i] - 1] += 1; // stages[i]번째 요소를 index로 해서 index가 나오면 그 방에 가서 1 더해주기
            }
        }

        int total = length;
        // 실패율 = 클리어 못함 / 각 스테이지 도전
        // 각 배열에서의 전체 개수
        double[] rate = new double[N]; // 실패율을 저장할 배열
        for (int i = 0; i < N; i++) {
            // rate[stage] = 실패율
            if (arr[i] == 0) { // 실패율이 0인 경우
                rate[i] = 0.0;
            } else {
                double percent = (double) arr[i] / total;
                total -= arr[i];
                rate[i] = percent;
            }
        }

        int[] answer = new int[N]; // 정답(index를 저장해 줄 배열)

        // percent(rate의 값)를 기준으로 정렬
        for (int i = 0; i < N; i++) {
            double max = -1;
            int target = 0;

            for (int j = 0; j < N; j++) {
                if (rate[j] > max) { // 최대보다 크면
                    max = rate[j];
                    target = j + 1; // index는 0번부터 시작이므로 1 더해줘야 함
                }
            }
            rate[target - 1] = -1; // 그 다음 최대값을 구하기 위함
            answer[i] = target;
        }
        return answer;
    }
}

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int length = stages.length;
        int[] arr = new int[N + 1]; //index에 stage, 저장된 값에 각 stage가 나온 횟수
        //각 스테이지에 해당하는 유저가 몇 명인지 저장
        for(int i=0; i<length; i++){ //인원수만큼 반복
            if (stages[i] <= N) { //각 스테이지에 머문다고 해서 스테이지를 깬 것은 아니기 때문에 if문을 넣어 필터링
                arr[stages[i] - 1] += 1; //각 스테이지에 몇 명이 있는지 저장
            }
        }
        //각 방의 번호는 1이 아니라 0부터 시작
        double[] rate = new double[N+1]; //실패율을 저장할 배열
        
        //[][0] index, [][1] 값
        //정렬. 실패율로 내림차순 정렬. 만약 같다면 번호 순 오름차순 정렬
        ArrayList<double[]> list = new ArrayList<>();
        
        int total = stages.length;
        for(int i=0; i<arr.length; i++){
            if(arr[i] == 0){
                rate[i] = 0.0;
            }else{
                double percent = (double) arr[i] / (double) total;
                total = total - arr[i]; //그 단계만큼의 인원을 빼기
                rate[i] = percent;
            }
            double[] indexAndRate = new double[2]; //double[0]에 index, double[1]에 rate 저장
            indexAndRate[0] = i+1; //스테이지 번호는 1부터 시작하기 때문
            indexAndRate[1] = rate[i];
            list.add(indexAndRate);
        }

        Collections.sort(list, new Comparator<double[]>(){ //arraylist안에서의 double형 배열을 가지고만 정렬을 할 것
            @Override
            public int compare(double[] o1, double[] o2){
                if(o1[1] == o2[1]){
                    return Double.compare(o1[0], o2[0]);
                }else{
                    return Double.compare(o2[1], o1[1]);
                }
            }
        });
        
        //정렬 후 
        int[] answer = new int[N];
        for(int i=0; i<N; i++){
            answer[i] = (int) list.get(i)[0];
        }
        
        return answer;
    }
}