2019 Kakao Blind CodeTest - 2. 실패율 자바(JAVA) 해설 및 정리

안녕하세요 .이번의 풀어볼 문제는 실패율입니다. 실패율은 객체 정렬을 통해서 문제를 해결합니다.

 

문제

2. 실패율

• 정답률: 55.57%
• 문제 풀러 가기

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

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

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

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

Nstagesresult

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

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]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

• [4,1,2,3]

문제 풀이 및 해설

일단 이문제의 경우 문제의 대한 이해를 하는데 조금 걸렸는데요.  

 

input 값의 경우 그 값이 뜻하는 것은 그 숫자의 스테이지까지 도달했다는 뜻이고, 그 이후 스테이지는 못 도착했다는 뜻입니다.

스테이지 N보다 n+1값을 가지는 경우 모든 스테이지를 다 정복했다는 뜻이 됩니다. 그리고 모든 스테이지의 실패율은 기본은 0으로 고정되어있고,  실패율은 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수를 뜻합니다. 

 

즉, 2가 3개있는 첫번째 경우에는 2번 스테이지의 실패율이 3/7이 됩니다. 왜냐면, 8명의 사용자가 1명은 1스테이지에서 막혀서 2번째 스테이지에 도착했거나 막혀있는 사람은 총 7명이 됩니다. 3명이 막혀있으므로 3/7 이 이 실패율이 됩니다.

 

그리고 난 다음에 이 실패율의 크기를 바탕으로 각 스테이지의 번호를 오름차순으로 (즉, 실패율이 높은 순으로 나열합니다.) 배열에 저장합니다.

 

제가 처음 부딪힌 난관은 이 두개를 동시에 묶는 방법을 생각하는게 어려웠습니다. 일단 자바는 pair를 이용하지 않는다면, 두개를 가볍게 묶을 수 있는 방법은(가볍게라고 하니까 좀 웃기긴하지만 한줄에 묶는 방법은 없으니) 없습니다. 저는 두개를 동시에 묶을 생각을 못하고 각각의 배열을 따로 따로 넣고 오름차순을 하니 index 번호가 지정되지 않았습니다. 그냥 오름 차순만 되버리게 되었습니다.

 

즉, 애초에 이 스테이지 index와  실패율 double을 같이 묶을 필요가 있다는 것이죠.

 

그래서 인덱스와 실패율을 node라는 클래스로 뺀 뒤에 같이 묶었습니다. 그리고 정렬하는 방식은 Comparable을 사용하던 Comparator를 이용해도 큰 상관은 없지만, 이 int와 double의 다른 인자를 처리하는 데 있어서는 Comparator를 이용하는 방식이 더 적합해 보여서 적용했습니다. 

 

자바에 익숙해지는데는 좀 더 시간이 필요하겠지만, Comparator를 이용할때는 기본형 타입 Double이나 Integer의 compare함수를 이용하는 것을 이용하는 것이 유용합니다.  그리고 이 경우 double타입이 같은 경우가 나올 수 도 있으므로 ==의 경우 integer의 따른 오름차순을 적용하든 내림 차순을 적용하는 방식을 취해야합니다. 

 

이런 실수를 범할 수도 있습니다.  double타입의 실패율을 그냥 빼버리고 return타입에 넣어버리면, 오름차순으로 정렬되지 않습니다. 왜냐하면 compare함수는 리턴타입이 int고 double타입을 빼서 return에 넣어버려도 0, -1, 1로 밖에 나올 수 밖에 없고, 0.5 0.7 -1.0와 같이 값이 나오지 않습니다.  (실제로 내가 한 실수)

 

그리고 난다음에 이 comparator를 Array.Sort에 그 값을 넣어주면 그에 따른 정렬된 값이 나오게 됩니다. 

 

코드

import java.util.Arrays;
import java.util.Comparator;

public class Solution {
    public static int[] solution(int n, int[] stages) {
    	int arr[] = new int[n+2];
    	node[] failRate = new node[n+1];
    	Arrays.fill(arr,0);
    	for(int i =0; i<stages.length; i++){
    		arr[stages[i]]++;
    	}
    	int total = stages.length;
    	failRate[0] = new node(0, -1.0);
    	for(int i =1; i<n+1; i++){
            if(total!=0){
                failRate[i] = new node(i, (double)arr[i] / total);
    		    total -= arr[i];
            }
            else{
                failRate[i] = new node(i, 0);
            }
     		
    	}
    	Comparator<node> f = new Comparator<node>(){
			@Override
			public int compare(node o1, node o2) {
				if(o1.failRate == o2.failRate){
					return Integer.compare(o1.idx, o2.idx);
				}
				return -Double.compare(o1.failRate, o2.failRate);
			}
    	};
    	Arrays.sort(failRate, f);
    	int [] answer = new int[n];
    	for(int i =0; i<n; i++){
    		answer[i] = failRate[i].idx;
    	}
    	
    	/*    	for(int i =1; i<n+1; i++){
 		failRate[i] = (double)arr[i] / total;
		total -= arr[i];
	}
	double[] failRateIndex =failRate.clone();
	Arrays.sort(failRate);
	for(int i=1; i<n+1; i++){
		for(int j=1; j<n+1; j++){

		}
	}*/
        return answer;  
    }
}

class node{
	int idx;
	double failRate;
	
	public node(int cnt, double failRate){
		this.idx = cnt;
		this.failRate = failRate;
	}
}