프로그래머스(실패율) - Java

[실패율]

https://programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

 

* 로직

• 스테이지의 번호와 실패율을 담을 클래스를 생성한다
• stages 배열을 하나씩 탐색하며 카운팅 정렬(arr[])을 진행한다. 스테이지의 전체 개수(total)도 담아둔다
• 사전에 카운팅 정렬된 배열을 이용해 스테이지의 번호를 1부터 N까지 차례대로 탐색한다
  
  • 스테이지에 도달한 유저가 없다면 -> 실패율은 0으로 정의한 후 우선순위 큐에 삽입
  • 유저가 존재한다면
    • arr[n]: n번째 스테이지에 도달했지만 클리어 못한 수
    • total -= arr[1~n]: 스테이지에 도달한 플레이어 수
• 우선순위 큐에 담긴 정보 중, 가장 첫번째 루트 정보를 출력한다

 

import java.util.PriorityQueue;

class StageInfo implements Comparable<StageInfo>{
    public double rate;    //실패율
    public int stageIdx;    //스테이지 번호

    public StageInfo(double rate, int stageIdx) {
        this.rate = rate;
        this.stageIdx = stageIdx;
    }

    @Override
    public int compareTo(StageInfo o) {
        if(this.rate < o.rate) return 1;
        else if(this.rate == o.rate) return this.stageIdx - o.stageIdx;
        return -1;
    }
}

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = {};
        int[] arr = new int[N+2];   //N+1이 들어오는 경우

        int total = 0;
        for(int stage : stages) {
            arr[stage]++;
            total++;
        }

        PriorityQueue<StageInfo> priorityQueue = new PriorityQueue<>();
        for(int n=1; n<=N; ++n) {
            double t = total;

            // 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
            if(arr[n] == 0) {
                priorityQueue.offer(new StageInfo(0, n));
            }

            else {
                double notClearNum = arr[n];   // 해당 스테이지에 도달했지만 클리어를 못한 수
                for(int i=1; i<n; ++i) {
                    t -= arr[i];    // 스테이지에 도달한 플레이어 수
                }

                priorityQueue.offer(new StageInfo(notClearNum/t, n));
            }
        }

        answer = new int[priorityQueue.size()];
        for(int i=0; i<answer.length; ++i) {
            answer[i] = priorityQueue.poll().stageIdx;
        }

        return answer;
    }
}