문제 풀이를 올리게 된 이유

풀다가 막혀서 인터넷을 봤는데, 하나같이 코드가 정말 읽기 힘들었다.
나는 바보에다가, 누군가가 떠먹여 주지 않으면 직접 퍼먹어야 직성이 풀리는 성격이라.
4시간에 걸쳐서 문제를 풀어보았다.

그리고 문제에서 제시된 변수명이 마음에 안들어서 바꾸었다. stages보다는 user들의 단계를 표현했다 생각해서 users로 바꾸었다. N도 n으로 바꾸고...

그리고 나름 예쁘게 푼 것 같아 자랑하고 싶었다. 😅

클래스 Stage

내 코드에서 주목할 만한 점은 Stage라는 class를 정의했다는 점이다.
귀찮아서 property에 private선언하고 getter/setter를 사용하지 않았다.

class Stage implements Comparable {
    int stageNumber;
    int count;
    double failureRate;

    public Stage(int stage) {
        this.stageNumber = stage;
    }

    @Override
    public int compareTo(Object o) {
        Stage otherStage = (Stage) o;
        if (this.failureRate == otherStage.failureRate) {
            return Integer.compare(this.stageNumber, otherStage.stageNumber);
        }
        return -Double.compare(this.failureRate, otherStage.failureRate);
    }
}

Stage 클래스는 다음의 변수를 가진다.

• stage 번호: stageNumber (사실 의미없는 값)
• 도달해 있는 user 수: count
• 실패율: failureRate

그리고 또 특이한 점은 Comparable Interface를 사용하였다.
개인적으로 Comparator/Comparable은 맘에 안든다. 뭐가 큰지를 코드를 작성하는 과정에서 알 수가 없다.
사실 내가 바보라서 아직도 이해 못하는 것일 수도있다.
결국 테스트를 일일이 돌려가며 맞는지 확인하는 절차가 필요했다.

나머지 풀이

stage에 유저를 넣을 때에는 최대 스테이지를 초과한 유저를 넣지 않았는데, ArrayIndexOutOfBoundException을 방지하기 위해서다.
Array의 경우 최대 인덱스를 벗어나면 Exception을 던지는건 Java 개발자라면 상식이니까...

// stage에 유저 넣기 (최대 스테이지를 통과한 사람은 넣지 않음)
for (int userStage : users) {
    if (userStage <= n) {
        stages[userStage - 1].count++;
    }
}

전체 user의 수를 Stage별로 차근차근 줄여나가며, Stage의 count나 userCount 중 하나가 0일 경우 Infinity, ArithmeticException 를 방지하기 위해, 그리고 문제의 조건을 만족하기 위해 0.0을 넣어주었다.

// 전체 user 수 구해서 Stage에 통과한 user수 넣기         
int userCount = users.length; 
for (Stage stage : stages) {
    if (stage.count == 0 || userCount == 0) {
        stage.failureRate = 0.0;
    } else {
        stage.failureRate = (double) stage.count / userCount;
        userCount -= stage.count;
    }
}

정렬의 경우는 Comparable을 구현했기 때문에 Arrays.sort()를 이용하여 간단히 정렬시켜주었다.

예상했던 시간복잡도는 nlogn 이었고, Stage의 sorting에서만 소요되므로 최대 500 개의 Record인 Stage를 정렬하는 것은 결과에 큰 영향을 주지 않을 것이라고 생각했다.

전체코드

import java.util.Arrays;

class Solution {
    public int[] solution(int n, int[] users) {
        int[] answer = new int[n];
        Stage[] stages = new Stage[n];

        // stage 초기화.
        for (int i = 0; i < n; i++) {
            stages[i] = new Stage(i + 1);
        }

        // stage에 유저 넣기 (최대 스테이지를 통과한 사람은 넣지 않음)
        for (int userStage : users) {
            if (userStage <= n) {
                stages[userStage - 1].count++;
            }
        }

        // 전체 user 수 구해서 Stage에 통과한 user수 넣기
        int userCount = users.length;
        for (Stage stage : stages) {
            if (stage.count == 0 || userCount == 0) {
                stage.failureRate = 0.0;
            } else {
                stage.failureRate = (double) stage.count / userCount;
                userCount -= stage.count;
            }
        }

        // stage 정렬
        Arrays.sort(stages);

        // stage 정렬된 것 answer에 넣기
        for (int i = 0; i < n; i++) {
            answer[i] = stages[i].stageNumber;
        }

        return answer;
    }

    class Stage implements Comparable {
        int stageNumber;
        int count;
        double failureRate;

        public Stage(int stage) {
            this.stageNumber = stage;
        }

        @Override
        public int compareTo(Object o) {
            Stage otherStage = (Stage) o;
            if (this.failureRate == otherStage.failureRate) {
                return Integer.compare(this.stageNumber, otherStage.stageNumber);
            }
            return -Double.compare(this.failureRate, otherStage.failureRate);
        }
    }
}

읽어주셔서 감사합니다.
재밌게 읽으셨다면, 댓글 달아주세요! 😆 ❤️도 환영합니다!