[프로그래머스] 실패율

1. 문제

---

2. 풀이 과정

---

• 문제의 기본 조건 정리
  • N: 스테이지 갯수
  • stages[i]: i번째 유저의 현재 스테이지
  • stages의 길이: 유저 수
  • 실패율[n]: 현재 n번째 스테이지에 있는 유저 수 / n번째 스테이지 이상인 유저 수
• 문제 접근 방식
  1. 각 스테이지에 대한 실패율을 구해 하나의 배열에 저장한다.
     • 실패율을 구하기 위해선 분자(현재 n번째 스테이지에 있는 유저 수)와 분모(n번째 스테이지 이상인 유저 수)를 구해야한다.
     • 각각을 구한 뒤 나누어서 배열에 저장하면 된다.
  2. 실패율 배열 정보를 가지고 높은 순으로 순서대로 결과 배열에 저장한다.

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        
        double dodal_cnt = 0; // 해당 stage에 도달한 유저 카운트
        double dojun_cnt = 0; // 해당 stage에 아직 도전 중인 유저 카운트 
        double[] fail_rate_arr = new double[N]; // 각 스테이지의 실패율을 담는 배열
         
        for(int stage = 1; stage <= N; stage++) {
            for(int j = 0; j < stages.length; j++) {
                if(stages[j] >= stage) { // j번째 유저가 해당 stage에 도달했는지(분모)
                    dodal_cnt++;
                    if(stages[j] == stage){ // j번째 유저가 해당 stage에 아직 도전 중인지(분자)
                        dojun_cnt++;
                    }     
                }
            }
            if(dodal_cnt == 0) { 
                fail_rate_arr[stage - 1] = 0; // 도달한 유저가 없으면 실패율은 0
            } else {
                double fail_rate = dojun_cnt / dodal_cnt;
                fail_rate_arr[stage - 1] = fail_rate; 
            }
            dojun_cnt = 0;
            dodal_cnt = 0;
        }
        
        int[] fail_rate_rank = new int[N];
        
        for(int i = 0; i < N; i++) {
            double max = Arrays.stream(fail_rate_arr).max().getAsDouble(); // 최댓값 뽑기
            for(int j = 0; j < N; j++) {
                if(fail_rate_arr[j] == max) {
                    fail_rate_rank[i] = j + 1; // 최댓값을 가지는 유저를 rank 배열에 넣기
                    fail_rate_arr[j] = -1; // 해당 유저는 더이상 따지면 안되므로 임의의 작은 값 넣기
                    break;
                }
            }
        }

        return fail_rate_rank;
    }
}

시간복잡도

• O(N^2)

---

사실 입력 값 중 stages의 최대 길이가 200,000이었기 때문에 O(N^2)으로 풀면 안되는 문제였다. 

그래도 다행히 정답처리는 됐지만 코드자체는 좋은 코드가 아니다. 

 

1차적으로 실패율을 구하는 코드에서부터 O(N^2) 미만으로 풀 방법이 떠오르지 않았다. 

또한 실패율을 1차적으로 뽑고 그 순서에 대한 정보를 별도의 배열로 저장하려고 할 때 그 방법이 잘 떠오르지 않았던 것 같다. 그렇다 보니 주먹구구식으로 억지로 답을 뽑아내게 되었다.

 

다른 정답 코드를 통해 어떻게 접근했어야 하는지 알아보자

4. 다른 정답 코드와 비교

---

『코딩 테스트 합격자 되기 - 자바편』 해설

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        
        // 각 스테이지를 도전하고 있는 플레이어 수를 각각 구함(분자)
        int[] challenger = new int[N + 2];
        for(int i = 0; i < stages.length; i++) {
            challenger[stages[i]]++;
        }
        
        // 스테이지별 실패한 사용자 수 계산 
        HashMap<Integer, Double> fails = new HashMap<>();
        double total = stages.length;
        
        // 스테이지를 순회하며 실패율 계산 
        for(int i = 1; i <= N; i++) { 
            if(challenger[i] == 0) { // 해당 스테이지에 도전중인 사람이 없는 경우 실패율은 0
                fails.put(i, 0.);
            }
            else {
                // 분모에 들어갈 스테이지에 도달한 플레이어 수는 
                // 이전 스테이지에 대해서 스테이지에 도달한 플레이어 수에서 도전 중인 플레이어 수를 뺀 값이다.
                fails.put(i, challenger[i] / total); 
                total -= challenger[i]; 
            }
            
        }
        
        // 해시맵을 value를 기준으로 내림차순 정렬 후 key값만 배열로 변환
        return fails.entrySet().stream().sorted(
                (o1, o2) -> Double.compare(
                    o2.getValue(), o1.getValue()
                )).mapToInt(HashMap.Entry::getKey).toArray();
    }
}

시간복잡도

• O(NlogN)

---

이 코드를 보고 감탄을 했다.

크게 두 가지 부분에 대해 감탄을 했는데 

1.  첫 번째는 나는 실패율의 분모에 들어갈 각 스테이지에 도달한 유저를 구하기 위해 stages 배열을 순회해 해당 stage 값보다 크거나 같으면 카운트를 해주는 식으로 풀었는데 이렇게 풀 이유가 전혀없었다. 그냥 분모는 이전 스테이지에 대해서 스테이지에 도달한 플레이어 수에서 도전 중인 플레이어 수를 뺀 값이었다. 이 것을 알았다면 그냥 O(N)으로 풀 수 있는 건데 바보짓을 했었다.
2. 두 번째는 해시맵을 사용하는 부분이다. 실패율을 구한 다음 큰 순서대로 별도의 배열에 저장하기 위해 뻘짓을 했는데 그냥 해시맵을 사용해 스테이지를 key값으로, 실패율 value값으로 함께 저장해 실패율을 기준으로 내림차순 정렬을 한 뒤 그 해시맵의 key값을 배열로 뽑아내면 됐었다. 이렇게 되면 정렬에 대한 부분만 따지면 되므로 시간복잡도가 O(NlogN)이 된다. 물론 해시맵을 다루는 부분은 다소 코드가 복잡하지만 익히기만 한다면 엄청난 성능향상을 이루어 낼 수 있다.

2번 부분을 stream을 사용하지 않고 풀어서 쓴다면

List<Map.Entry<Integer, Double>> entries = new ArrayList<>(fails.entrySet()); // 맵의 각 엔트리에 대해 순서를 확보하기 위해 List로 변환
entries.sort((o1, o2) -> Double.compare(o2.getValue(), o1.getValue())); // 내림 차순 정렬

int[] result = new int[entries.size()];
for(int i = 0; i < result.length; i++) {
    result[i] = entries.get(i).getKey(); // 키 값 배열로 옮기기 
}