[프로그래머스] Lv.1 실패율 (Java)

문제

나의 풀이

• int[] challengers : i번째 스테이지를 현재 도전 중인 사용자의 수
• int[] acheivers : i번째 스테이지에 도달한 사용자의 수
  -> achivers[i] = acheivers[i+1]+challengers[i];

i번째 스테이지에 도달한 사용자 수를 구하려면 현재 그 스테이지를 도전 중인 사용자 수에 그 스테이지보다 더 높은 스테이지를 도전 중인 모든 사용자 수를 더하면 된다.

• double[] failRate : failRate[i] => i번째 스테이지의 실패율
  -> failRate[i] = challengers[i]/acheivers[i]

• HashMap<Double,LinkedList<Integer>> failRateMap : 실패율을 key로, 해당 실패율을 가진 스테이지 번호 리스트를 value로 갖는 hashmap

각 스테이지 1부터 N까지의 실패율을 구하여 failRate[]에 넣는다.
failRateMap에는 그 실패율에 해당하는 스테이지 번호 리스트의 맨 뒤에 넣는다.
-> 스테이지 1부터 실패율을 구하기 때문에, 같은 실패율을 가지는 스테이지가 있다면 리스트에 작은 번호가 제일 앞에 오게 된다.

이 때 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다. 에 대한 처리를 반드시 해주어야 한다.
-> 나는 이걸 안 해서 계속 통과를 못 했다 ...😇

모든 스테이지의 실패율을 구한 뒤, Arrays.sort()를 이용해 failRate를 정렬한다.

정렬된 failRate에서 실패율을 하나씩 가져와 map에서 해당 실패율을 가진 스테이지 번호 리스트를 가져온다.
리스트가 빌 때까지 리스트의 맨 앞에서 값을 가져와 정답 배열에 넣는다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] challengers = new int[N+2];
        // 1<=i<=N+1 일 때 현재 스테이지 i번을 도전중인 플레이어의 수
        int[] achievers = new int[N+2];
        // 1<=i<=N+1 일 때 스테이지 i번에 도달한 플레이어의 수
        double[] failRate = new double[N+1];
        // 1<=i<=N 일 때 스테이지 i번의 실패율
        HashMap<Double,LinkedList<Integer>> failRateMap = new HashMap<>();
        // <실패율,해당 실패율을 가진 스테이지번호 list>

        challengers[0]=0;
        for(int i=0;i<stages.length;i++) {
            challengers[stages[i]]++;
        }

        achievers[N+1] = challengers[N+1];
        for(int i=N;i>0;i--) {
            achievers[i] = achievers[i+1] + challengers[i];
        }

        for(int i=1;i<N+1;i++) {
            double rate = challengers[i]==0? 0:(double)challengers[i]/achievers[i];
            if(!failRateMap.containsKey(rate)) {
                failRateMap.put(rate, new LinkedList<>());  
            }
            failRateMap.get(rate).add(i);
            failRate[i] = rate;
        }

        // map에 들어있는 key(실패율)가 큰 순서대로 가져오고, 해당 value list에서 스테이지 번호를 가져온다.
        // 이미 list에는 스테이지 번호가 작은 순서대로 들어가 있으니 head에서부터 poll하여 정답 배열에 넣는다.

        int[] answer = new int[N];
        int idx = 0;
        Arrays.sort(failRate);

        for(int i=failRate.length-1;i>0;i--) {
            LinkedList<Integer> stageList = failRateMap.get(failRate[i]);
            while(!stageList.isEmpty()) {
                answer[idx++] = stageList.poll();
            }
        }

        return answer;
    }
}

후기

막상 다 풀고나니 은근 어렵지 않은 문제였던 것 같은데 ..
처음에 acheivers의 정의를 이상하게 내려서 많이 헤맸던 문제였다.
얼마나 걸렸는지는 기억도 안 나거니와 하고 싶지도 않다 ^___^