[프로그래머스] 실패율 자바 리스트 정렬, 객체

문제

N : 실패율 조사대상 전체 스테이지의 갯수

stages : 현재 사람들의 도달 스테이지 (진행 중)

실패율 : 현재 스테이지 진행 중인 사람 수 / 해당 스테이지에 도달 및 통과한 플레이어의 수

 

해당 스테이지에 도달한 플레이어가 없는 경우 실패율은 0.

 

각 스테이지 별 실패율을 계산하고 실패율이 높은 순으로 내림차순 정렬한 배열을 반환하시오.

단 실패율이 서로 같은 경우, 작은 번호의 스테이지가 먼저 위치할 것.

 

제한사항

stages에는 1 이상 N + 1 이하의 자연수가 담겨있다

접근

각 스테이지에 도달한 플레이어의 수 현황을 Map에 담고 이에 근거해 실패율을 계산하는 로직을 구상하였으나

실패율에 근거해 정렬하는 부분에서 막혔다.

public int[] solution(int N, int[] stages) {
        int[] answer = {};

        int totalMans = stages.length;
        int maxStage = 0;
        int minStage = 1;
        Map<Integer, Integer> stageInfo = new HashMap<>();
        for(int s : stages){
            int v = stageInfo.get(s) == null ? 1 : stageInfo.get(s) + 1;
            stageInfo.put(s, v);
            maxStage = Math.max(maxStage, s);
        }

        int maxRate = 0;
        int minRate = Integer.MAX_VALUE;
        StringBuilder minRateStage = new StringBuilder();
        StringBuilder maxRateStage = new StringBuilder();
        Map<Integer, Integer> failRates = new HashMap<>();

        for(int i = minStage; i < maxStage; i ++){
            int thisCnt = stageInfo.get(i) == null ? 0 : stageInfo.get(i);
            int rate = thisCnt / totalMans;
            if(thisCnt > 0){

                totalMans -= thisCnt;
            }
            failRates.put(i, rate);
            minRate = Math.min(minRate, rate);
            maxRate = Math.max(maxRate, rate);

            if(maxRate == rate){
                maxRateStage.append(i);
            } else if(minRate == rate){
                minRateStage.append(i);
            }
        }

        return answer;
    }

해결방안

1. stages에는 1 ~ N + 1 까지 오는 점에 착안하여 Map 대신 int[N+2] 배열에 집계하는 것이 편리할 것.
2. 실패율을 계산할 때 int 가 아닌 double로 정확한 값을 계산할 것.
3. 실패율 정보를 담을 때, Map이 아닌 스테이지와 실패율을 인스턴스로 갖는 별도의 객체를 생성하고 이를 List에 담는 것이 직관적임.
4. Collections를 활용해 리스트를 정렬한 후 answer에 담아 마무리 짓는다.

 

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        //도전자 수 계산
        int[] peoples = new int[N + 2];
        for(int stage : stages){
            peoples[stage] ++;
        }

        //실패율 계산
        List<Stage> stageList = new ArrayList<>();
        int total = stages.length;

        for(int i = 1; i <= N; i++){
            double failRate = total == 0 ? 0 : (double) peoples[i] / total;
            stageList.add(new Stage(i, failRate));
            total -= peoples[i];
        }

        //실패율로 정렬
        Collections.sort(stageList, (a, b) -> {
           if(a.failRate == b.failRate) {
               return a.num - b.num;
           }
           return Double.compare(b.failRate, a.failRate);
        });

        int[] answer = new int[N];
        for(int i = 0; i < N; i++){
            answer[i] = stageList.get(i).num;
        }

        return answer;
    }
}

class Stage {
    int num;
    double failRate;
    
    public Stage(int num, double failRate){
        this.num = num;
        this.failRate = failRate;
    }
}

알게된 점

1. 각 항목마다 여러 정보를 다루어야 하는 경우 ( 문제처럼 스테이지 번호와 실패율 )
별도의 객체를 Class로 만들고 관리하면 쉽다.

2. List의 내림차순 정렬과 상세조건처리 
- 내림차순 : Collections.sort(list, (a, b) -> {return Double.compare(b.failRate, a.failRate)});
- 특정 조건에서는 오름차순 정렬 추가
Collections.sort(stageList, (a, b) -> {
    if(a.failRate == b.failRate) { // 실패율이 같은경우
         return a.num - b.num;
// 양수 반환: a.num > b.num → a가 뒤로 정렬 (오름차순)
// 음수 반환: a.num < b.num → a가 앞으로 정렬
// 0 반환: 같은 값 (여기서는 이미 실패율이 같다는 조건 하에 처리)
    } return Double.compare(b.failRate, a.failRate);
});