Programmers School level 1: 실패율

<풀기 전 생각>

sort()함수를 사용하여 유저들의 클리어 스테이지 정보를 정렬시키고

각 스테이지의 실패율을 float 타입으로 실제로 구하고 차후 반복문을 이용해 높은 순서대로 인덱스를 뽑아 반환 할 계획을 세우고 문제 풀이에 들어 갔다.

 

<중간 문제점>

 float의 표현 범위는 소수 7번째 자리 까지 임으로 그 이상의 자리 수에서 차이가 난 경우는 비교하는게 불가능 하여

1 , 6, 7, 9, 13, 14, 23, 24, 25, 26 에서 오류가 발생하였고

 double 로 고쳐도 Pass가 되지 않아 좀더 고민하게 되었다.

 

<실패한 코드>

class Solution {
    public int[] solutionFail(int N, int[] stages) {
        int[] answer = new int[N];
        int maxPeople = stages.length;
        double[] failureRate = new double[N];
        int i=0; int j=0;
        Arrays.sort(stages); // n*log n
        // 전체 스테이지 탐색
        for(int stage=1;stage<=N;stage++) {
            // 실패율의 분자
            int numerator = 0;
            for (i = 0; i < maxPeople; i++) {
                if(stage==stages[i])
                    numerator++;
                if(stage<stages[i])
                    break;
            }
            // 예외 처리
            if(i==0)
                failureRate[stage] = 0;
            else{
                // 실패율의 분모 (통과한 인원 수)
                int denominator = maxPeople-i+numerator;
                failureRate[stage-1] = (double) numerator/denominator;
            }
        }
        System.out.println("qf");
        for(i=0;i<answer.length;i++) {
            double tmp = -1; int index=-1;
            for (j = 0; j < failureRate.length; j++) {
                if(tmp<failureRate[j]){
                    tmp=failureRate[j];
                    index = j;
                }
            }
            failureRate[index] = -1;
            answer[i] = index+1;
        }
        return answer;
    }

}

 

애초에 비교방식을 실수가 아닌 분자*분모 이런 식으로 정수 끼리 비교할 경우 정확한 비교가 가능하다고 판단하여

코드를 수정했으나 

1 ,6, 7, 13, 23, 24, 25가 계속해서 성공하지 않았고 

 

고민 한 결과 분자가 0이 된 경우 실패율이 0임을 처리하니

최종적으로 23, 24을 제외하고는 pass 하게 되었고

 

추가적으로 고민하다 문제에서 정수의 범위는 1~200000 임을 보게 되었고

int 형으로는 200000 * 200000 의 수를 전부 표현 하는게 불가능 하다는 생각이 들게 되어 

long 타입으로 바꾸어서 푸니 비로서 pass 할 수 있었다.

 

<최종 코드>

시간 복잡도 O(n*m) 공간 복잡도 O(n)

class Solution {
    public int[] solution(int N, int[] stages) {
        // 정수 범위를 벗어나는 경우 때문에 안됨
        int[] answer = new int[N];
        int maxPeople = stages.length;
        // 분자, 분모 순으로 저장
        long[][] failureRate = new long[N][2];
        int i=0; int j=0;
        Arrays.sort(stages); // n*log n
        // 전체 스테이지 탐색
        int numerator,denominator;
        for(int stage=1;stage<=N;stage++) {
            // 실패율의 분자
            numerator = 0;
            for (i = 0; i < maxPeople; i++) {
                if(stage==stages[i])
                    numerator++;
                if(stage<stages[i])
                    break;
            }
            // 실패율의 분모 (통과한 인원 수)
            if(numerator==0)
                denominator=1;
            else
                denominator = maxPeople-i+numerator;
            //failureRate[stage-1] = (float) numerator/denominator;
            failureRate[stage-1][0] = numerator;
            failureRate[stage-1][1] = denominator;
        }
        System.out.println("qf");
        for(i=0;i<answer.length;i++) {
            long tmp[] = {-1,1}; int index=-1;
            for (j = 0; j < failureRate.length; j++) {
                if(tmp[0]*failureRate[j][1]<failureRate[j][0]*tmp[1]){
                    tmp[0]=failureRate[j][0];
                    tmp[1]=failureRate[j][1];
                    index = j;
                }
            }
            failureRate[index][0] = -1;
            failureRate[index][1] = 1;
            answer[i] = index+1;
        }

        return answer;
    }
}

 메모: 우수 풀이를 보니 해당 인터페이스를 구체화 하여 문제를 해결 하였는데 추가 학습할 필요가 있어 보인다.

+ double도 결국에는 소수점 16자리 까지 표현이 불가능 한거로 알아서 미묘한 오차가 생길 줄 알았는데 예상 외 였다.

Comparable<Stage>