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

프로그래머스 실패율 - JAVA

---

문제 설명

1. 프랜즈 오천성의 기존 사용자 사이에 스테이지 차이가 너무 커 신규 사용자 수가 급감했다.
2. 이에 해결 방법으로 동적으로 게임 시간을 늘려 난이도 조절을 하기로 하였다.
3. 실패율을 스테이지에 도달했으나 아직 클러어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수로 정의한다.
4. 전체 스테이지의 개수 N, 게임을 이요하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 떄, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 retrun.

제한 사항

1. 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
2. stages의 길이는 1 이상 200,000 이하이다.
3. stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
   • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
   • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
4. 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
5. 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

문제 풀이

1. 각 스테이지에 몇명의 유저가 있는지 저장.
2. 최초의 stages배열의 길이가 1번 스테이지에 도전한 사용자이며, 각 스테이지의 실패율을 구한 뒤 해당 스테이지의 사용자 수를 뺌으로 다음 스테이지의 총 도전자 수를 알 수 있음.
3. 각 스테이지의 사용자 수를 pass_user(스테이지 총 도전 사용자)를 나눔으로 실패율을 구하고, 몇번째 스테이지였는지 저장.
   • 이후 실패율을 기준으로 정렬을 하며, 스테이지 번호도 저장되어야 하여 Pair class를 만들고 정렬 기준을 만듬.
4. 실패율을 기준으로 Pair class 리스트를 정렬
5. 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return.

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {        
        int[] users = new int[N + 2]; // 1
        for (int n : stages) {
            users[n]++;
        }

        int pass_user = stages.length; // 2
        List<Pair> failure = new ArrayList<>(); // 3

        for (int i = 1; i <= N; i++) { // 3
            failure.add(new Pair((double)users[i] / pass_user, i));
            pass_user -= users[i]; // 2
        }

        Collections.sort(failure); // 4

        int[] answer = new int[N]; // 5
        for (int i = 0; i < N; i++) {
            answer[i] = failure.get(i).index;
        }

        return answer;
    }

    class Pair implements Comparable<Pair>{
        double failure;
        int index;

        public Pair(double failure, int index) {
            this.failure = failure;
            this.index = index;
        }

        @Override
        public int compareTo(Pair o) {
            if (this.failure > o.failure) {
                return -1;
            } else if (this.failure < o.failure) {
                return 1;
            } else {
                return 0;
            }
        }
    }
}