[프로그래머스] Lv.1 : 실패율 - 자바[Java]

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

프로그래머스

 

풀이

1 <= N <= 500

1 <= 플레이어 수(M) <= 200,000

 

stages[] 배열을 사용하여 각 스테이지마다 성공한 플레이어 수와 실패한 플레이어 수를 카운트하는 로직을 사용하였으며, 이 로직의 시간복잡도는 O(NM) = 10^9이므로 가능하다.

 

int[] success: success[i]는 i번 스테이지에 성공한 사람 수

int[] fail: fail [i]는 i번 스테이지에 실패한 사람 수

실패율 = fail[i] / (success[i] + fail[i])

 

 

로직

1. stages[] 배열을 사용하여 각 스테이지마다 성공한 플레이어 수와 실패한 플레이어 수를 카운트 한다.

2. 각 스테이지마다 실패율을 구해 ArrayList<Data> list에 추가한다.

3. list를 정렬한 후, 정렬한 순서대로 스테이지 번호를 answer 배열에 저장한다.

 

주의할 점

실패율을 구할 때, success[i] + fail[i]가 0이 될 수 있으므로, 런타임 에러에 주의한다.

코드

import java.util.*;

class Solution {
    static class Data implements Comparable<Data> {
        int stage;
        double failPercent;
        
        public Data(int s, double fp) {
            stage = s;
            failPercent = fp;
        }
        
        @Override
        public int compareTo(Data o) {
            if (this.failPercent == o.failPercent) {
                return this.stage - o.stage;
            }
            else if (this.failPercent > o.failPercent)
                return -1;
            else return 1;
        }
    }
    
    public int[] solution(int N, int[] stages) {
        int[] success = new int[N+1];
        int[] fail = new int[N+2];
        
        // 성공한 플레이어 수와 실패한 플레이어 수 카운트
        for (int stage: stages) {
            for (int i = 1; i < stage; i++) {
                success[i]++;
            }
            fail[stage]++;
        }
        
        // 실패율을 구해 list에 추가
        ArrayList<Data> list = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            double total = (double)(success[i] + fail[i]);
            double failPercent = 0;
            if (total > 0)
                failPercent = fail[i] / total;
            list.add(new Data(i, failPercent));
        }
        
        Collections.sort(list); // 정렬
        
        // 정답 배열 구하기
        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            Data d = list.get(i);
            answer[i] = d.stage;
        }
        
        return answer;
    }
}

 

수정한 풀이

배열을 2개 사용할 필요 없이, (실패한 사람 수 = 현재 스테이지 도착한 사람 수 - 다음스테이지 도착한 사람 수)이므로, 각 스테이지마다 도착한 사람 수만 저장하면 된다.

실패율 = (people[i] - people[i+1]) / people[i]

import java.util.*;

class Solution {
    static class Data implements Comparable<Data> {
        int stage;
        double failPercent;
        
        public Data(int s, double fp) {
            stage = s;
            failPercent = fp;
        }
        
        @Override
        public int compareTo(Data o) {
            if (this.failPercent == o.failPercent) {
                return this.stage - o.stage;
            }
            else if (this.failPercent > o.failPercent)
                return -1;
            else return 1;
        }
    }
    
    public int[] solution(int N, int[] stages) {
        int[] people = new int[N+2];
        
        for (int stage: stages) {
            for (int i = 1; i <= stage; i++)
                people[i]++;
        }
        
        ArrayList<Data> list = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            double failPercent = 0;
            if (people[i] > 0)
                failPercent = (double)(people[i] - people[i+1]) / people[i];
            list.add(new Data(i, failPercent));
        }
        
        Collections.sort(list);
        
        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            Data d = list.get(i);
            answer[i] = d.stage;
        }
        
        return answer;
    }
}

 

다른 풀이

O(NM) 대신 O(N) or O(M)의 풀이로 풀 수 있다.

import java.util.*;

class Solution {
    static class Data implements Comparable<Data> {
        int stage;
        double failPercent;
        
        public Data(int s, double fp) {
            stage = s;
            failPercent = fp;
        }
        
        @Override
        public int compareTo(Data o) {
            if (this.failPercent == o.failPercent) {
                return this.stage - o.stage;
            }
            else if (this.failPercent > o.failPercent)
                return -1;
            else return 1;
        }
    }
    
    public int[] solution(int N, int[] stages) {
        int[] failPlayers = new int[N+2]; // 각 스테이지마다 실패한 플레이어 수
        int players = stages.length; // 전체 플레이어 수
        
        for (int stage: stages) {
            failPlayers[stage]++;
        }
        
        ArrayList<Data> list = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            double failPercent = 0;
            // players는 현재 스테이지에 도착한 플레이어 수다.
            // 처음은 모든 플레이어가 1층에 도착하거나 클리어했다.
            // 현재 스테이지에 실패한 플레이어 수를 빼서 계속해서 다음 스테이지에 도착한 플레이어 수를 구한다.
            if (players > 0)
                failPercent = (double)failPlayers[i] / players;
            players -= failPlayers[i];
            list.add(new Data(i, failPercent));
        }
        
        Collections.sort(list);
        
        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            Data d = list.get(i);
            answer[i] = d.stage;
        }
        
        return answer;
    }
}

 

왼쪽이 수정한 풀이, 오른쪽이 다른 풀이다. 대부분의 테스트케이스에서 걸린 시간이 줄여진 것을 확인할 수 있다.