[42889] 실패율

✔ 실패율

[프로그래머스 42889]

문제 분석하기

각 스테이지의 실패율을 구해 실패율이 높은 스테이지부터 내림차순으로 배열에 담아 반환하도록 함

이때 각 스테이지의 실패율은 '스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수'

 

예) [2, 1, 2, 6, 2, 4, 3, 3]

stages[i]	arr[5][2]
2는 1 스테이지 클리어 O, 2 스테이지 클리어 X	[[0, 1], [1, 1], [0, 0], [0, 0], [0, 0]]
1은 1 스테이지 클리어 X	[[1, 2], [1, 1], [0, 0], [0, 0], [0, 0]]
2는 1 스테이지 클리어 O, 2 스테이지 클리어 X	[[1, 3], [2, 2], [0, 0], [0, 0], [0, 0]]
6은 1, 2, 3, 4, 5 스테이지 클리어 O	[[1, 4], [2, 3], [0, 1], [0, 1], [0, 1]]
2는 1 스테이지 클리어 O, 2 스테이지 클리어 X	[[1, 5], [3, 4], [0, 1], [0, 1], [0, 1]]
4는 1, 2, 3 스테이지 클리어 O, 4 스테이지 클리어 X	[[1, 6], [3, 5], [0, 2], [1, 2], [0, 1]]
3은 1, 2 스테이지 클리어 O, 3 스테이지 클리어 X	[[1, 7], [3, 6], [1, 3], [1, 2], [0, 1]]
3은 1, 2 스테이지 클리어 O, 3 스테이지 클리어 X	[[1, 8], [3, 7], [2, 4], [1, 2], [0, 1]]
실패율(failure)은	[[1, 1/8], [2, 3/7], [3, 2/4], [4, 1/2], [5, 0]] 이므로 실패율을 기준으로 내림차순 정렬한 후, 같다면 작은 번호의 스테이지가 먼저 오도록 함 [3, 4, 2, 1, 5]

손으로 풀어보기

1. 도전 중인 스테이지의 번호에 따라 스테이지 도전 중, 스테이지 클리어를 저장
   • 스테이지 번호가 i일 경우 i - 1까지의 스테이지는 클리어이므로 i - 1[1] 증가
   • 스테이지 번호가 i일 경우 i 스테이지는 도전 중이므로 i[0] 증가
2. 스테이지 도전 중, 스테이지 클리어 배열을 이용해 스테이지 실패율을 스테이지 번호와 함께 저장
   • '스테이지 도전 중 / 스테이지 클리어'를 함께 계산하여 스테이지 번호와 함께 저장
   • 만약 스테이지 클리어가 없다면 0으로 그대로 놔줌
3. 스테이지 실패율을 기준으로 내림차순 정렬한 후, 실패율이 같다면 작은 번호의 스테이지가 먼저 오도록 하여 스테이지 번호 반환

슈도코드 작성하기

N(전체 스테이지의 개수)
stages(게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열)
answer(실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열)
arr(스테이지 도전 중인 사용자의 수와 스테이지 클리어 사용자의 수를 담은 배열)
for(i -> stages만큼) {
    for(j -> 0 ~ i - 1만큼) {
    if(모든 스테이지를 클리어 했다면)
        for(j -> 0 ~ i - 1만큼)
            클리어한 스테이지이므로 arr[j][1] 증가
    }
    else {
        for(j -> 0 ~ i만큼)
            클리어한 스테이지이므로 arr[j][1] 증가
        도전하는 스테이지이므로 arr[i - 1][0] 증가
    }
}
failure(스테이지의 번호와 실패율을 담은 배열)
for(i -> arr만큼) {
    failure[i][0]에 스테이지 번호인 i + 1 저장
    if(클리어한 사용자가 있다면) 
        failure[i][1]에 스테이지 실패율인 arr[i][0] / arr[i][1] 저장
}
failure를 실패율을 기준으로 내림차순 정렬한 후, 실패율이 같다면 작은 번호의 스테이지가 먼저 오도록 정렬 커스텀
failures의 스테이지 번호를 순서대로 answer에 저장
answer 반환

코드 구현하기

/**
 * 42889) 실패율
 */
public class L040_42889 {
    // N(전체 스테이지의 개수)
    // stages(게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열)
    public int[] solution(int N, int[] stages) {
        // answer(실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열)
        int[] answer = new int[N];
        // arr(스테이지 도전 중인 사용자의 수와 스테이지 클리어 사용자의 수를 담은 배열)
        // 배열 대신 HashMap을 사용해 시간복잡도 낮추기 가능
        int[][] arr = new int[N][2];
        for (int i : stages) {
            // 모든 스테이지를 클리어 했다면
            if (i == N + 1) {
                // 클리어한 스테이지들 증가
                for (int j = 0; j < i - 1; j++)
                    arr[j][1]++;
            }
            // 모든 스테이지를 클리어하지 못했다면
            else {
                // 클리어한 스테이지들 증가
                for (int j = 0; j < i; j++)
                    arr[j][1]++;
                // 현재 도전하는 스테이지 증가
                arr[i - 1][0]++;
            }
        }
        // failure(스테이지의 번호와 실패율을 담은 배열)
        double[][] failure = new double[N][2];
        for (int i = 0; i < arr.length; i++) {
            // 스테이지 번호 저장
            failure[i][0] = i + 1;
            // 클리어한 사용자가 있다면
            if (arr[i][1] != 0)
                // 스테이지 실패율을 계산해서 저장 (클리어한 사용자가 없다면 그대로 실패율은 0)
                failure[i][1] = (double) arr[i][0] / arr[i][1];
        }
        // failure를 실패율을 기준으로 내림차순 정렬한 후,
        // 실패율이 같다면 작은 번호의 스테이지가 먼저 오도록 정렬 커스텀
        Arrays.sort(failure, new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                int result = Double.compare(o2[1], o1[1]);
                if (result == 0)
                    return Double.compare(o1[0], o2[0]);
                return result;
            }
        });
        // failures의 스테이지 번호를 순서대로 answer에 저장
        for (int i = 0; i < failure.length; i++) {
            answer[i] = (int) failure[i][0];
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L040_42889 solution = new L040_42889();

        int N = 2;
        int[] stages = { 1, 1, 1, 1 };

        int[] result = solution.solution(N, stages); // [1, 2]

        System.out.println(Arrays.toString(result));
    }
}