프로그래머스 실패율 JAVA 풀이 (정렬, 구현)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

게임의 각 스테이지마다 실패율을 계산한 뒤 실패율이 높은 순서대로 스테이지 번호를 정렬하는 문제이다.

실패율은 다음과 같이 정의된다.

실패율 = 현재 스테이지에 도달했지만 아직 클리어하지 못한 사용자 수 / 현재 스테이지에 도달한 사용자 수
실패율이 같다면 스테이지 번호가 작은 순으로 정렬해야 한다.

---

📌 접근 방법

각 스테이지에 머물러 있는 사용자 수를 카운팅 배열에 저장한다.

그 후 전체 사용자 수를 기준으로 각 스테이지의 실패율을 계산한다.

 

현재 스테이지에서 실패한 사용자 수를 전체 도달 인원에서 제외하면서 다음 스테이지의 도달 인원을 구할 수 있다.

계산한 실패율과 스테이지 번호를 객체에 저장한 뒤 정렬하여 결과를 반환한다.

---

📌 핵심 아이디어

1. 각 스테이지 사용자 수 카운팅

int[] count = new int[N + 2];

for (int stage : stages) {
    count[stage]++;
}

예시

stages = [2,1,2,6,2,4,3,3]

count[1] = 1
count[2] = 3
count[3] = 2
count[4] = 1
count[5] = 0
count[6] = 1

 

2. 실패율 계산

int players = stages.length;

for (int i = 1; i <= N; i++) {
    double rate = 0;

    if (players != 0) {
        rate = (double) count[i] / players;
    }

    players -= count[i];
}

예시

1번 스테이지
실패 인원 : 1
도달 인원 : 8
실패율 : 1 / 8

players = 8 - 1 = 7

2번 스테이지
실패 인원 : 3
도달 인원 : 7
실패율 : 3 / 7

players = 7 - 3 = 4

 

3. 정렬 조건 설정

list.sort((a, b) -> {
    if (a.rate == b.rate) {
        return a.number - b.number;
    }
    return Double.compare(b.rate, a.rate);
});

정렬 기준

1. 실패율 내림차순
2. 실패율이 같으면 스테이지 번호 오름차순

---

📌 전체 코드

import java.util.*;

class Solution {

    static class Stage {
        int number;
        double rate;

        Stage(int number, double rate) {
            this.number = number;
            this.rate = rate;
        }
    }

    public int[] solution(int N, int[] stages) {

        int[] count = new int[N + 2];

        for (int stage : stages) {
            count[stage]++;
        }

        List<Stage> list = new ArrayList<>();

        int players = stages.length;

        for (int i = 1; i <= N; i++) {

            double rate = 0;

            if (players != 0) {
                rate = (double) count[i] / players;
            }

            list.add(new Stage(i, rate));

            players -= count[i];
        }

        list.sort((a, b) -> {
            if (a.rate == b.rate) {
                return a.number - b.number;
            }
            return Double.compare(b.rate, a.rate);
        });

        int[] answer = new int[N];

        for (int i = 0; i < N; i++) {
            answer[i] = list.get(i).number;
        }

        return answer;
    }
}

---

📄 정리

• 실패율은 현재 스테이지 실패 인원 / 해당 스테이지 도달 인원으로 계산한다.
• 카운팅 배열을 이용하면 각 스테이지 인원을 빠르게 구할 수 있다.
• 현재 스테이지 계산 후 실패 인원을 제외하면서 다음 스테이지 도달 인원을 구한다.
• 정렬 조건은 실패율 내림차순, 스테이지 번호 오름차순이다.
• 구현과 정렬을 함께 활용하는 대표적인 문제이다.