[프로그래머스] 실패율

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

문제 요약

스테이지 N개에 대한 실패율 내림차순으로 구하기

접근

stages 배열에 사용자가 현재 머물고 있는 stage가 있다.
실패율은 (도전하고 있는 사용자)/(도전하고 있는 사용자 & 통과한 사용자)
분모에 들어가는 인원을 구하기 위해 이진 탐색을 이용했다.

stages 배열 [2, 1, 2, 6, 2, 4, 3, 3] 을 정렬 시키면 [1, 2, 2, 2, 3, 3, 4, 6]
만약 2의 실패율을 구해본다면 3/7이 나와야 한다.

2의 lowerBound => 1, upperBound => 4, stages 배열의 길이 : 8
즉 (upperBound - lowerBound) / (stages - lowerBound) 로 구하면 된다.

위의 방법으로 각 스테이지(1~N)를 루프를 돌아 구한 후, 정렬하면 된다.
다음 코드와 같다.

import java.util.*;
import java.io.*;

class Pair<A, B> {
    public A first;
    public B second;

    public Pair(A first, B second) {
        this.first = first;
        this.second = second;
    }
}

class Solution {
    
    public int[] solution(int N, int[] stages) {
        int[] answer = {};
        
        int[] board = new int[N+3];
        for(int i = 0; i < N; i++) {
            board[i] = i + 1;
        }
        
        Arrays.sort(stages);
        ArrayList<Pair<Double, Integer>> v = new ArrayList<>();
        
        for(int i = 0; i < N; i++) {
            int num = board[i];
            int low = lowerBound(num, stages);
            int upper = upperBound(num, stages);
            
            double res = 0.0;
            res = (double)(upper - low) / (stages.length - low);
            if (Double.isNaN(res)) {
                res = 0.0;
            }
            
            System.out.println(num + " " + res + " Low : " + low + " Upper : " + upper);
            
            int index = i+1;
            v.add(new Pair<>(res, index));
        }

        v.sort(Comparator.comparing(p -> p.first, Comparator.reverseOrder()));
        
        
        return v.stream().mapToInt(p -> p.second).toArray();
        
    }
    
    private static int lowerBound(int num, int[] stages) {
        int l = -1;
        int r = stages.length;
        
        while (l + 1 < r) {
            int mid = (l+r) / 2;
            if (stages[mid] < num) l = mid;
            else r = mid;
        }
        
        return r;
    }
    
    private static int upperBound(int num, int[] stages) {
        int l = -1; 
        int r = stages.length;
        
        while (l + 1 < r) {
            int mid = (l+r) / 2;
            if (stages[mid] > num) r = mid;
            else l = mid;
        }
        
        return r;
    }
}

stages 배열(길이 M)을 정렬 - O(MlogM)
lower,upperBound - O(logM) -> 이를 N번 하기에 O(NlogM)
v 정렬 - O(NlogN)
총 O(MlogM + NlogM)이 된다.

실행 결과는 다음과 같다.

다시 생각

정답은 맞았지만 위의 사진처럼 이는 상당한 시간을 요구했다. 이 문제에는 비효율적이라 생각했고 이를 카운팅 배열과 Map을 사용해 다시 구성해보았다.

stages 배열을 딱 한 번만 순회해 각 스테이지에 머물러 있는 사용자 수를 미리 계산한다.
-> board[stages[i]] += 1
stages 배열을 훑으면서 board 배열에 스테이지별 도전자 수를 카운트 하는 것

코드는 다음과 같다.

import java.util.*;
import java.io.*;

class Solution {
    
    public int[] solution(int N, int[] stages) {
        int[] answer = {};
        
        int[] board = new int[N+3];
        for(int i = 0; i < stages.length; i++) {
            board[stages[i]] += 1; // board는 stages를 도전하고 있는 인원의 수
        }
        
        HashMap<Integer, Double> m = new HashMap<>();
        
        int cnt = stages.length; // 인원
        
        // 실패율 계산
        for(int i = 1; i <= N; i++) {
            if(board[i] == 0) m.put(i, 0.0);
            else {
                m.put(i, (double)board[i] / cnt);
                cnt -= board[i]; // 현재 스테이지 인원을 감소시켜야함
            }
        }
        
        // 실패율(key:value 중 value) 기준 내림차순
       return m.entrySet()
            .stream()
            .sorted((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()))
            .mapToInt(map -> map.getKey())
            .toArray();
    }
    
    
}

board 배열을 순회해 각 스테이지에 머물러 있는 사용자 수 계산 (길이 M의 stages 순회) : O(M)
각 스테이지 실패율 계산 : O(N)
실패율 기준 정렬 : O(NlogN)
큰 항만 고려해서 -> O(M + NlogN)

실행 결과는 다음과 같다.

첫 번째 풀이와 비교해봤을 때 반복문 내에서 수행되는 연산의 비용을 최소화 해야 했다.