[2019 KAKAO BLIND RECRUITMENT] 실패율(JAVA)

코딩테스트 연습 - 실패율

우선순위큐를 활용해서 실패율이 높은 순서대로 정렬하고 실패율이 같을 경우 스테이지가 낮은 순서대로 정렬될 수 있도록 하였다.

각 스테이지에 도달한 사람과 실패한 사람의 숫자는 Stage의 역순으로 for문을 돌면서 구해줬다.

예제 1

예제 1로 살펴보면 다음과 같다.

실패율은 Stage에 도달한 사람의 수 / Sum으로 계산하면 된다.

 

※ Sum이 0일 경우의 예외 처리를 해주자!

 

 

import java.util.PriorityQueue;
 
public class 실패율 {
    static class Ratio implements Comparable<Ratio> {
        double ratio;
        int stage;
 
        Ratio(double ratio, int stage) {
            this.ratio = ratio;
            this.stage = stage;
        }
 
        @Override
        // 실패율이 높은 순으로 정렬, 실패율이 같으면 stage가 작은 순으로 정렬
        public int compareTo(Ratio o) {
            if (this.ratio == o.ratio)
                return Integer.compare(this.stage, o.stage);
            return -Double.compare(this.ratio, o.ratio);
        }
    }
 
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        
        // 각 스테이지의 카운트를 세어주기 위한 배열
        // N개의 스테이지가 있을 때 N+1 스테이지에 도달한 사람이 있을 수 있으므로 N+2 크기로 잡아준다. 
        int[] stage_cnt = new int[N + 2];
 
        for (int stage : stages) {
            stage_cnt[stage]++;
        }
        
        PriorityQueue<Ratio> ratio = new PriorityQueue<Ratio>();
        int sum = stage_cnt[N + 1];
        for (int i = N; i > 0; i--) {
            sum += stage_cnt[i];
 
            double r = 0;
            
            // sum이 0일 경우 예외 처리
            if (sum != 0)
                r = (double) stage_cnt[i] / (double) sum;
 
            ratio.add(new Ratio(r, i));
        }
 
        int idx = 0;
        while (!ratio.isEmpty()) {
            answer[idx++] = ratio.poll().stage;
        }
 
        return answer;
    }
}