[프로그래머스 코딩테스트] 실패율(Java)

  문제 설명

  슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

  이 문제를 어떻게 할까 고민한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

• 실패율은 다음과 같이 정의한다.
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

  전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 ㅜ주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

 

  제한사항

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

 

  입출력 예

N	stages	result
5	[2, 1, 2, 6, 2, 4, 3, 3]	[3, 4, 2, 1, 5]
4	[4, 4, 4, 4, 4]	[4, 1, 2, 3]

import java.util.Arrays;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] array = new int[N + 2];
        for (int i = 0; i < stages.length; i++) {
            array[stages[i]]++;
        }
        double[] probability = new double[array.length];
        probability[1] = (double) array[1] / stages.length;
        int sum = 0;
        for (int i = 2; i < array.length - 1; i++) {
            sum += array[i - 1];
            if (stages.length - sum == 0) {
                probability[i] = 0.0;
            } else {
                probability[i] = (double) array[i] / (stages.length - sum);
            }
        }
        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            int maxIdx = 0;
            double maxFailureRate = -1.0;
            for (int j = 1; j <= N; j++) {
                if (probability[j] > maxFailureRate) {
                    maxFailureRate = probability[j];
                    maxIdx = j;
                }
            }
            answer[i] = maxIdx;
            probability[maxIdx] = -1.0;
        }
        return answer;
    }
}

  배열 array를 생성합니다. 배열의 크기는 N + 2로 지정합니다. 스테이지는 1번부터 시작하므로 0번 인덱스를 제외하였으며, 모든 스테이지를 클리어한 유저의 경우 N + 1을 원소로 가지므로 이를 고려했습니다.

  for문이 stages의 길이만큼 순회합니다.

  array의 stages의 i 번째 원소가 증가합니다. 이는 각 스테이지별로 클리어한 인원을 세기 위함입니다.

  배열 probablity를 생성합니다. 크기는 array로 지정합니다. 변수명대로 실패율을 담기 위한 배열이므로 double형으로 정했습니다.

  array의 1번째 원소를 stages의 길이만큼 나누어 구한 실패율을 probablity의 1번 인덱스에 할당합니다.

  변수 sum을 생성합니다. 이는 앞선 스테이지 클리어에 실패한 인원을 제외하기 위해 만든 변수입니다.

  for문이  2부터 array의 길이만큼 순회합니다.

  sum에 array의 i - 1 번째 원소를 더하기 할당합니다.

  if문에서 stages의 길이  - sum이 0과 같다면 probablity의 i 번째 원소에 0.0을 할당합니다. 아무도 성공하지 못했다는 뜻입니다. 분모를 0으로 나누어 발생하는 오류를 방지하기 위함이기도 합니다.

  그렇지 않다면 probability의 i 번째 원소에 array의 i 번째 원소에 stages의 길이에 sum을 뺀 값을 나눈 뒤 double형으로 형변환 합니다.

  배열 answer를 생성하고 크기를 N으로 지정합니다.

  바깥 for문이 N까지 순회합니다.

  변수 maxIdx와 maxFailureRate를 생성합니다. 각각 0과 -1.0로 초기화합니다.

  안쪽 for문이 1부터 N까지 순회합니다.

  if문에서 probability의 j 번째 원소가 maxFailureRate보다 크다면 maxFailureRate에 probability의 j 번째 원소를 할당합니다. maxIdx에는 j를 할당합니다.

  answer의 i 번째 원소에 maxIdx를 할당하여 스테이지를 기록합니다.

  probability의 maxIdx 번째 원소에는 -1.0을 할당하여 중복으로 할당되지 않도록 합니다.