실패율

안녕하세요, 오늘은 저번 시간에 이어서 계속 코딩 테스트 연습 문제를 풀이해보도록 하겠습니다.
이번에 풀이할 문제는 2019 카카오 블라인드 채용에서 출시되었던 문제이니 꽤 난이도가 있습니다.

📚 문제 설명

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 

그녀가 만든 프렌즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다.

원인은 신규 사용자와 기존 사용자 사이에 스테이지 사이가 너무 큰 것이 문제였다.

 

이 문제를 어떻게 할까 고민한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다.

역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다.

 

실패율의 공식은 (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수)

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때

실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

코딩테스트 연습 - 실패율

📸 제한 사항

1) 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.

2) stages의 길이는 1 이상 200,000 이하이다.

3) stages에는 1 이상 N+1 이하의 자연수가 담겨있다.

- 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
- 단, N+1은 마지막 스테이지(N 번째 스테이지)까지 클리어 한 사용자를 나타낸다.

4) 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 앞에 오도록 한다.

5) 스테이지에 도달한 유저가 없을 경우 해당 스테이지의 실패율은 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]

첫 번째 입출력 예시에서 총스테이지의 개수는 1부터 5까지이며 stages 배열을 통해 사용자들의 스테이지 상태를 전달받습니다. 먼저 첫 번째 스테이지의 실패율과 같은 경우는 위에서 말했던 공식에 따라 스테이지에 도달한 플레이어 수가 8명이며 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수는 1명이기에 1/8이라는 값이 나와 이를 약분해 실패율이 대략 0.1%가 나옵니다.

 

위와 동일한 방식으로 두 번째, 세 번째, 네 번째, 다섯 번째 스테이지의 실패율을 구한다면 각각 0.4%, 0.5%, 0.5%, 0%가 나오게 되며 그 후 실패율이 높은 순서대로 내림차순 방식으로 스테이지를 정렬하면 3, 4, 2, 1, 5 순으로 스테이지가 각각 정렬되게 됩니다.

 

두 번째 입출력 예시 또한 위에서 설명했던 첫 번째 입출력 예시와 같은 방식으로 문제를 풀이할 수 있기에 구체적인 설명은 생략하고 제가 직접 종이에 풀이했던 내용을 사진 찍어 올려 설명을 대체하도록 하겠습니다. 어렵지 않으니 스스로 천천히 해보시기 바랍니다.

📨 나의 해결책 (1시간 30분 소요)

# solution 메소드

먼저 solution 메소드는 매개변수로 스테이지의 개수 N과 사용자들의 현재 스테이지 상태를 알려줄 stages 배열을 매개변수로 전달받습니다. 또한 각 스테이지 별 실패율을 저장할 failureRateList를 선언했으며 checkFailureRate를 호출해 값을 초기화합니다.

 

그 후 각 스테이지 별 실패율을 내림차순으로 정렬한 resultStages 배열을 reverseStages 메소드를 호출해 값을 초기화하며 최종적으로 resultStages 배열을 반환해 프로그램을 종료합니다. solution 메소드에서는 따로 복잡한 로직 처리를 진행하지 않습니다.

public int[] solution(int N, int[] stages) {
    ArrayList<Double> failureRateList = checkFailureRate(N, stages);
    int[] resultStages = reverseStages(failureRateList);
    return resultStages;
}

# checkFailureRate 메소드

checkFailureRate 메소드는 각 스테이지 별 실패율을 계산하는 역할을 하며 solution 함수로부터 매개변수로 스테이지의 개수 N과 사용자들의 현재 스테이지 상태를 알려줄 stages 배열을 전달 받습니다. 또한 내부의 로직은 각 스테이지 별로 스테이지에 도달한 플레이어 수와 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수를 활용해 실패율을 구하여 리스트를 반환합니다.

public ArrayList<Double> checkFailureRate(int N, int[] stages) {
    ArrayList<Double> failureRateList = new ArrayList<>();

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

        for (int j = 0; j < stages.length; j++) {
            if (stages[j] == i) notCompletePlayer++;
            if (stages[j] >= i) reachPlayer++;
        }
        if (notCompletePlayer == 0) failureRateList.add((double) 0);
        else failureRateList.add(((double) notCompletePlayer / reachPlayer));
    }
    return failureRateList;
}

# reverseStages 메소드

reverseStages 메소드는 매개변수로 각 스테이지 별 실패율이 담긴 failureRateList를 전달받으며 이를 활용하여 각 스테이지 별 실패율이 높은 순서대로 내림차순 방식으로 스테이지를 정렬하는 역할을 합니다. 먼저 descFailureRateList를 만들어 매개변수로 전달받은 failureRateList를 복사합니다. 그 후 descFailureRateList를 내림차순으로 정렬하고 반복문을 활용하여 기존의 failureRateList와 조합해 resultStages 배열에 실패율이 높은 순서대로 각 스테이지 번호를 저장하여 이를 반환합니다.

public int[] reverseStages(ArrayList<Double> failureRateList) {
    int[] resultStages = new int[failureRateList.size()];

    ArrayList<Double> descFailureRateList = (ArrayList<Double>) failureRateList.clone();
    descFailureRateList.sort(Comparator.reverseOrder());

    for (int i = 0; i < failureRateList.size(); i++) {
        resultStages[i] = failureRateList.indexOf(descFailureRateList.get(i))+1;
        failureRateList.set(failureRateList.indexOf(descFailureRateList.get(i)), (double) -1);
    }
    return resultStages;
}

[ 전체 소스코드 ]

class Solution {

    public int[] solution(int N, int[] stages) {
        ArrayList<Double> failureRateList = checkFailureRate(N, stages);
        int[] resultStages = reverseStages(failureRateList);
        return resultStages;
    }

    public ArrayList<Double> checkFailureRate(int N, int[] stages) {
        ArrayList<Double> failureRateList = new ArrayList<>();

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

            for (int j = 0; j < stages.length; j++) {
                if (stages[j] == i) notCompletePlayer++;
                if (stages[j] >= i) reachPlayer++;
            }
            if (notCompletePlayer == 0) failureRateList.add((double) 0);
            else failureRateList.add(((double) notCompletePlayer / reachPlayer));
        }
        return failureRateList;
    }

    public int[] reverseStages(ArrayList<Double> failureRateList) {
        int[] resultStages = new int[failureRateList.size()];

        ArrayList<Double> descFailureRateList = (ArrayList<Double>) failureRateList.clone();
        descFailureRateList.sort(Comparator.reverseOrder());

        for (int i = 0; i < failureRateList.size(); i++) {
            resultStages[i] = failureRateList.indexOf(descFailureRateList.get(i))+1;
            failureRateList.set(failureRateList.indexOf(descFailureRateList.get(i)), (double) -1);
        }
        return resultStages;
    }
}

🎨 모범 답안

이번 문제의 모범 답안은 아래와 같습니다. 위에서 제가 구현했던 코드와는 사뭇 다른 점이 존재하지만 내부의 로직은 거의 비슷한 형태로 구현되어있습니다. 실제 코드를 컴파일해보면 앞에서 제가 구성했던 코드보다 속도는 훨씬 빠르게 기록되지만 코드의 가독성과 함수로 분리되지 않은 점은 아쉬웠던 것 같습니다. 그러나 이렇게 코드를 구현할 생각을 했다는 것이 정말 창의적인 것 같습니다.

public class Solution {

    public static class Stage implements Comparable<Stage> {
        int id;
        double failure;

        public Stage(int id, double failure) {
            this.id = id;
            this.failure = failure;
        }

        @Override
        public int compareTo(Stage o) {
            if (failure < o.failure ) {
                return -1;
            }
            if (failure > o.failure ) {
                return 1;
            }
            return 0;
        }
    }

    public int[] solution(int N, int[] lastStages) {
        int nPlayers = lastStages.length;
        int[] nStagePlayers = new int[N+2];

        for (int stage : lastStages) {
            nStagePlayers[stage] += 1;
        }

        int remainingPlayers = nPlayers;
        List<Stage> stages = new ArrayList<>();
        for (int id = 1; id <= N; id++) {
            double failure = (double) nStagePlayers[id] / remainingPlayers;
            remainingPlayers -= nStagePlayers[id];

            Stage s = new Stage(id, failure);
            stages.add(s);
        }
        stages.sort(Collections.reverseOrder());

        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            answer[i] = stages.get(i).id;
        }
        return answer;
    }
}

👍 글을 마치며

오늘은 2019 카카오 블라인드 채용에서 출제된 실패율이라는 문제를 풀어보았습니다. 처음에는 이 문제를 풀 때 겁이 많이 났으나 실제로 로직을 설계하고 구현할 때는 크게 어렵지 않게 문제를 풀 수 있었습니다. 이 과정 속에서 문제를 이해하고 설계하는 부분이 정말 중요하다는 것을 느꼈습니다.지금까지 저는 꾸준히 코딩 테스트 연습 문제를 풀어보고 있으나 카카오의 코딩 테스트 문제만큼 문제를 풀이할 때 재미있는 문제는 없는 것 같습니다. 문제의 스토리가 기업의 카카오프렌즈 캐릭터로 대체적으로 구성되어 문제 이해에 많은 도움이 되며 문제를 풀이할 때도 더욱 적극적인 자세로 풀 수 있어 저는 카카오 코딩 테스트 문제를 푸는 것을 좋아합니다.