[프로그래머스/Java] 실패율

문제

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

프로그래머스

N개의 스테이지로 구성된 게임이 있다.

이 게임의 실패율은 다음과 같이 정의한다.

• 스테이지에 도달했으나 아직 클리어하지 못한 플레이어 수 / 스테이지에 도달한 플레이어 수

스테이지의 개수 `N`과 게임을 이용하는 사용자가 현재 멈춰 있는 스테이지의 번호가 담긴 배열 `stages`가 주어졌을 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담긴 배열을 반환해야 한다.

• 1 ≤ `N` ≤ 500
• 1  ≤ `stages` ≤ 200,000 (`N+1`번 스테이지는 마지막 스테이지까지 클리어 한 사용자를 나타낸다.)
• 실패율이 같으면 작은 스테이지 번호가 먼저 와야 한다.
• 스테이지에 도달한 유저가 없으면 실패율은 `0` 

풀이

생각보다 문제 풀이에 필요한 데이터를 구성하는 것이 까다로운 문제였다.

 

실패율을 계산하기 위해 필요한 '`i`번째 스테이지에 있는 유저의 수'를 구하는 건 쉬운 일이니 어렵지 않게 넘어갔지만 이상하게 '`i`번째 스테이지에 도달한 유저의 수'를 어떻게 구할지 잘 떠오르지 않았다.

 

처음에는 이중 for 문을 사용해 현재 스테이지의 바로 다음 스테이지부터 모든 플레이어 수를 구해 `i`번째 스테이지에 도달한 유저의 수 `reachedPlayers[i]`를 구하는 코드를 작성했는데, 그럴 필요없이 먼저 모든 사용자의 수인 `totalPlayers`에서 현재 스테이지에 있는 유저의 수를 빼주어 스테이지에 도달한 유저의 수를 구하는 것이 더욱 효율적이었다.

 

그 다음 실패율을 계산하여 실패율을 내림차순으로 정렬한 뒤, 스테이지의 번호를 배열에 담아야 했다.

 

실수끼리의 비교는 정밀도의 오류 때문에 연산자를 통해 직접 비교하면 정확한 결과를 얻을 수 없다. `Double.compare(a, b)` 메서드를 사용했다.

 

오차 범위인 EPSILON을 두고 비교하는 방법도 있다. 두 수의 오차 범위가 아주 작다면 같은 값으로 판단하는 방식도 있다. JS에서는 전통적으로 이런 방식을 사용한다.

static final double EPSILON = 1e-9;

if (Math.abs(a - b) < EPSILON) {
    // a와 b는 거의 같다
}

 

최종적으로 반환해야 하는 건, 실패율을 기준으로 정렬한 스테이지 번호다. 스테이지 번호를 실패율로 내림차순 정렬한 뒤, 실패율이 같은 경우에도 정렬을 해줘야 해서 정렬의 조건이 다소 복잡하다.

 

복합적인 기준으로 정렬하기 위해, 스테이지 번호와 실패율 정보를 담은 `StageInfo` 객체를 `List`에 담아 문제의 기준에 맞게 정렬한 다음, 스테이지 번호만 배열로 담아 반환해준다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        // 현재 스테이지를 도전중인 플레이어 수를 계산한다.
        int[] currentUsers = new int[N + 2]; // 1 ~ N + 1까지 클리어한 사용자 수
        for (int stage : stages) {
            if (stage <= N) currentUsers[stage]++;
        }
        
        int totalPlayers = stages.length;
        List<StageInfo> stageInfos = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (totalPlayers == 0) {
                stageInfos.add(new StageInfo(i, 0));
            } else {
                double rate = (double) currentUsers[i] / totalPlayers;
                stageInfos.add(new StageInfo(i, rate));
                totalPlayers -= currentUsers[i]; // 다음 스테이지로 넘어간 사람만 남긴다.
            }
        }

        stageInfos.sort((a, b) -> {
            if (Double.compare(b.failureRate, a.failureRate) != 0) {
                return Double.compare(b.failureRate, a.failureRate); // 실패율을 기준으로 내림차순 정렬
            }
            return Integer.compare(a.stage, b.stage); // 스테이지 번호를 기준으로 오름차순 정렬
        });

        int[] result = new int[N];
        for (int i = 0; i < N; i++) {
            result[i] = stageInfos.get(i).stage;
        }

        return result;
    }
    
    static class StageInfo {
        int stage;
        double failureRate;

        StageInfo(int stage, double failureRate) {
            this.stage = stage;
            this.failureRate = failureRate;
        }
    }
}