[코딩테스트합격자되기-자바편] 문제06. 실패율

💡 해당 풀이는 코딩 테스트 합격자되기 - 자바편 에서 발췌된 내용을 바탕으로 작성되었습니다.

 

문제

출처: 프로그래머스 - 실패율

 

내용

 

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌습니다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감했기 때문입니다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였습니다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했습니다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았습니다. 오렐리를 위해 실패율을 구하는 코드를 완성하세요.

• 실패율 정의 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어집니다 이 때 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 반환하도록 solution() 함수를 완성하세요.

 

제약 사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수입니다.
• stages의 길이는 1 이상 200,000 이하이입니다.
• stages에는 1 이상 N + 1 이하의 자연수가 있습니다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타냅니다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타냅니다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오면 됩니다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 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번 스테이지에는 총 8명의 사용자가 도전했으며 이 중 1명의 사용자가 아직 클리어하지 못했습니다. 따라서 1번 스테이지의 실패율은 다음과 같습니다.

• 1 번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했습니다. 따라서 2번 스테이지의 실패율은 다음과 같습니다.

• 2 번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같습니다.

• 3 번 스테이지 실패율 : 2/4
• 4번 스테이지 실패율 : 1/2
• 5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같습니다.

• [3, 4, 2, 1, 5]

두 번째 입출력 예를 보면 모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0입니다.

• [4, 1, 2, 3]

 

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

• 통과 stage 체크하기
• 실패 stage 체크하기
• 스테이지별 실패율 계산하기
• 실패율 내림차순으로 정렬해서 인덱스 반환하기

 

풀이

 

풀이 시간

시작 시각	종료 시각	총 소요 시간
22:14	23:22	68분

 

문제 분석

 

제약 사항 파악 & 테스트 케이스 작성

• 스테이지의 개수 N은 1 이상 500 이하의 자연수입니다.
• stages의 길이는 1 이상 200,000 이하이입니다.
• stages에는 1 이상 N + 1 이하의 자연수가 있습니다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타냅니다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타냅니다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오면 됩니다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 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]

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(N, stages) {
    try = new int[N]
    success = new int[N]
    for (stage: stages) {
        for (i <= stage) {
            try[i-1] += 1
            success[i-2] += 1
        }
    }
    fail = new int[N]
    for (i < N) {
        // 0 체크 필요
        // 실패율
        fail[i] = success[i] / try[i]
    }

    // 실패율 정렬
    return 정수형배열
}

 

 

구현

import java.util.Arrays;

class Solution {
    public int[] solution(int N, int[] stages) {
        double[] tried = new double[N + 1];
        double[] failed = new double[N + 1];

        for (int stage : stages) {
            for (int i = 0; i < stage; i++) {
                if (i + 1 <= stage) {
                    tried[i] += 1;
                }
                if (i + 1 == stage) {
                    failed[i] += 1;
                }
            }
        }

        double[][] failRate = new double[N][2];
        for (int i = 0; i < N; i++) {
            if (tried[i] == 0) {
                failRate[i][1] = i + 1;
                continue;
            }
            failRate[i][0] = Double.valueOf(failed[i] / tried[i]);
            failRate[i][1] = i + 1;
        }

        // 실패율 내림차순, 스테이지 번호 오름차순으로 정렬
        Arrays.sort(failRate, (a, b) -> {
            if (a[0] != b[0]) {
                return Double.compare(b[0], a[0]); // 실패율 내림차순
            }
            return Double.compare(a[1], b[1]); // 스테이지 번호 오름차순
        });

        // 정렬된 스테이지 번호만 추출
        return Arrays.stream(failRate)
                    .mapToInt(x -> (int) x[1])
                    .toArray();
    }
}

 

 

복기하기

답안과 나의 풀이를 비교해보세요

import java.util.HashMap;

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

        // 1. 스테이지별 도전자 수를 구함
        int[] challenger = new int[N + 2];
        for (int stage : stages) {
            challenger[stage] += 1;
        }

        // 2. 스테이지 별 실패한 사용자 수 계산
        HashMap<Integer, Double> fails = new HashMap<>();
        double total = stages.length;

        // 3. 각 스테이지를 순회하며, 실패율 계산
        for (int i = 1; i <= N; i++) {
            if (challenger[i]== 0) { // 4. 도전한 사람이 없는 경우, 실패율은 0
                fails.put(i, 0.);
            } else {
                fails.put(i, challenger[i] / total); // 5. 시랲율 구함
                total -= challenger[i]; // 6. 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌
            }
        }

        return fails.entrySet().stream()
            .sorted((o1, o2) -> Double.compare(o2.getValue(), o.getValue()))
            .mapToInt(HashMap.Entry::getKey)
            .toArray();
    }
}

• challenger 배열을 초기화하고 각 스테이지 도전자 수 계산 시 시간 복잡도는 O(N + M)
• 스테이지 별로 실패율을 계산하는 데 필요한 시간 복잡도는 O(N)
• 실패율을 기준으로 스테이지 정렬 시 시간 복잡도는 O(NlogN)
• 연산 모두 고려 시 시간 복잡도는 총 O(M + NlogN)

 

요약하기

• challengers 와 total 만 있어도 간단하게 풀렸을 건데 생각을 못했다.
• int / int 는 int 형으로 반환하는 것을 주의하자.