실패율

Posted on Edited on In , ,

문제정의

유저가 스테이지를 어디까지 완료하였는지 담아놓은 배열 stage와 총 스테이지 개수 N이 주어질 때, 실패율을 계산하여 내림차순으로 정렬한다. 만약 실패율이 같은 경우 스테이지 번호가 작은 순서를 우선으로 한다. 실패율을 계산하는 수식은 다음과 같다.

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

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;

public class FailRate {

    //프로그래머스 문제풀이 level1 실패율
    public static void main(String[] args)
    {
        int N = 4;
        int[] stages = {4, 4, 4, 4, 4};
        Integer[] answer = new Integer[N];
        int[] clear = new int[N+2];
        double[] fail_rate = new double[N+1];
        for(int stage : stages)
        {
            for(int i = 1; i < stage; i++)
                clear[i]++;
        }
        clear[0] = stages.length;
        for(int i = 1; i <= N; i++)
        {
            if(clear[i-1] == 0)
                fail_rate[i] = 0;
            else
                fail_rate[i] = (double)(clear[i-1]-clear[i]) / (double)clear[i-1];
        }
        for(int i = 1; i <= N; i++)
            answer[i-1] = i;
        Arrays.sort(answer, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                if(fail_rate[o1] < fail_rate[o2])
                    return 1;
                else if(fail_rate[o1] > fail_rate[o2])
                    return -1;
                else
                    return Integer.compare(o1, o2);
            }
        });
    }
    
}
부분부분 살펴보자 
1
2
3
4
5
for(int stage : stages)
{
    for(int i = 1; i < stage; i++)
        clear[i]++;
}
스테이지를 클리어하는 사람 수를 저장해두는 배열 clear를 선언한다. stage-1이 여태까지 클리어해온 스테이지이므로 1부터 stage-1까지 clear를 1씩 올린다. 이 부분에서 시간복잡도는 stages의 길이를 m이라 할 때 \(O(N*m)\)이다.

1
2
3
4
5
6
7
8
clear[0] = stages.length;
for(int i = 1; i <= N; i++)
{
    if(clear[i-1] == 0)
        fail_rate[i] = 0;
    else
        fail_rate[i] = (double)(clear[i-1]-clear[i]) / (double)clear[i-1];
}

실패율을 계산하는 부분이다. i번째 스테이지에 도달한 사람은 clear[i-1]이다. 3레벨에 도달하는 사람이 2레벨을 통과한 사람인 것처럼(아직 3단계를 통과한 사람들은 아니다!). 지금은 성공률이 아닌 실패율을 계산하는 것이므로 이 사람들 중 통과한 사람의수가 분자에 들어가야한다. 따라서 clear[i-1]-clear[i]가 분자에 올라간다. 스테이지를 통과한 사람이 없을 경우엔 실패율을 0으로 한다. 이 부분에서 시간복잡도는 \(O(N)\)이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 1; i <= N; i++)
    answer[i-1] = i;
Arrays.sort(answer, new Comparator<Integer>(){
    @Override
    public int compare(Integer o1, Integer o2){
        if(fail_rate[o1] < fail_rate[o2])
            return 1;
        else if(fail_rate[o1] > fail_rate[o2])
            return -1;
        else
            return Integer.compare(o1, o2);
    }
});

정렬방식이 특이하게 주어진 경우에는 비교자를 직접 정의하는 것이 좋다. 대신 자바에서는 Integer, Double과 같은 Wrapper 클래스만 비교자 정의를 허용한다. 따라서 int라면 Integer로 꼭 바꿔주자. 자세한 비교 코드는 위 코드를 참고하자. 이 부분에서 시간복잡도는 \(O(NlogN)\)이다.

따라서 최종적인 시간복잡도는 \(O(N*m)\)이다.

테스트