[Java] 실패율 Lv1

실패율

문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를 github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.

출처: Programmers
실패율

풀이

첫번째 풀이

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];                          //정답 배열의 크기
        int[] comeStage = new int[N];
        int[] failStage = new int[N];
        double[] failPercent = new double[N];

        for(int i=0; i<stages.length; i++) {                //전달 된 각 플레이어가 현재 도전하고 있는 스테이지의 번호를 하나씩 추출
            for(int j=0; j < stages[i]; j++){               //도전하고 있는 스테이지 전까지의 도달인원을 계산
                if(j == N){
                    continue;   //이 부분은 N과 j가 같다는 것은 모든 스테이지를 통과 했다는 것이므로 해당 플레이어는 올클리어로 판단하고 끝냄
                }
                comeStage[j]++; //해당 스테이지에 몇명의 플레이어가 도달했는지 저장 하는 배열
            }
            if(stages[i] > N){
                continue;       //스테이지배열에 들어있는 플레이어의 값이 총 스테이지의 수보다 크면 올 클리어로 판단하고 넘김
            }
            failStage[stages[i] - 1]++;
        }

        // for(int i=0; i<comeStage.length; i++) {
        //     System.out.println(comeStage[i]);  
        // }

        // for(int i=0; i<comeStage.length; i++) {
        //     System.out.println(failStage[i]);  
        // }
        int stageNumber = 1;
        for(int i=0; i<N; i++) {
            failPercent[i] = (double)failStage[i] / (double)comeStage[i];
            answer[i] = stageNumber++;
        }

        // for(int i=0; i<comeStage.length; i++) {
        //     System.out.println(failPercent[i]);
        // }

        for (int i = 0; i < N - 1; i++) {
            for (int j = 1 + i; j < N; j++) {
                int tempValue = 0;
                double tempPercent;
                if (failPercent[i] < failPercent[j]) {
                    tempValue = answer[i];
                    answer[i] = answer[j];
                    answer[j] = tempValue;

                    tempPercent = failPercent[i];
                    failPercent[i] = failPercent[j];
                    failPercent[j] = tempPercent;
                }
                else if(failPercent[i] == failPercent[j]) {
                    if (answer[i] > answer[j]){
                        tempValue = answer[i];
                        answer[i] = answer[j];
                        answer[j] = tempValue;
                        tempPercent = failPercent[i];
                        failPercent[i] = failPercent[j];
                        failPercent[j] = tempPercent;
                    }
                }
            }
        }
        return answer;
    }
}

정렬 부분은 두번째 풀이에서 설명하고 먼저 어떤 데이터가 필요한지 정리했다.
“실패율이 높은 순서대로 내림차순으로 정렬”
Stage 갯수 : N
각 스테이지 도달인원: A
실패인원: B
실패율: B÷A 를 구해서 정렬하면 된다.

테스트 케이스

스테이지의 수: 5
각 플레이어의 도달 스테이지 번호: {2, 1, 2 ,6 ,2 ,4 ,3 ,3}

stage번호	1	2	3	4	5
도달인원	8	7	4	2	1
실패인원	1	3	2	1	0
실패율	1/8	3/7	2/4	1/2	0

현재 상태로 구해진 데이터를 주어진 조건대로 내림차순으로 정렬하면

stage번호	3	4	2	1	5
실패율	2/4	1/2	3/7	1/8	0

이렇게 정렬된 {3, 4, 2, 1, 5} 가 정답이다.

두번째 풀이

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];                          //정답 배열의 크기
        int[] comeStage = new int[N];
        int[] failStage = new int[N];
        double[] failPercent = new double[N];
        
        for(int i=0; i<stages.length; i++) {                //전달 된 각 플레이어가 현재 도전하고 있는 스테이지의 번호를 하나씩 추출
            for(int j=0; j < stages[i]; j++){               //도전하고 있는 스테이지 전까지의 도달인원을 계산
                if(j == N){
                    continue;   //이 부분은 N과 j가 같다는 것은 모든 스테이지를 통과 했다는 것이므로 해당 플레이어는 올클리어로 판단하고 끝냄
                }
                comeStage[j]++; //해당 스테이지에 몇명의 플레이어가 도달했는지 저장 하는 배열
            }
            if(stages[i] > N){
                continue;       //스테이지배열에 들어있는 플레이어의 값이 총 스테이지의 수보다 크면 올 클리어로 판단하고 넘김
            }
            failStage[stages[i] - 1]++;
        }
        int stageNumber = 1;    //aswer에 저장할 스테이지 번호 초기화. 스테이지는 0번이 없으므로 1부터 시작
        for(int i=0; i<N; i++) {    //실패율을 구해서 answer배열에 저장해 줌
            failPercent[i] = (double)failStage[i] / (double)comeStage[i];
            answer[i] = stageNumber++;  //도출해야 하는 값은 실패율에 따른 스테이지 번호이기 때문에 스테이지 번호 answer배열에 저장해줌
        }

        //answer배열의 실패율을 비교해서 정렬(사용한 정렬은 삽입정렬)
        for (int i = 0; i < N - 1; i++) {
            for (int j = 1 + i; j < N; j++) {
                int tempValue = 0;  //temp변수 두개는 스왑을 위한 임시변수
                double tempPercent = 0;

                if (failPercent[i] <= failPercent[j]) { //내림차순으로의 정렬을 위한 부분
                    if (failPercent[i] == failPercent[j] && answer[i] < answer[j]) { //두 개의 실패율이 같다면 stage번호가 더 낮은 것을 앞으로 해서 정렬한다.
                        continue;
                    }
                    tempValue = answer[i];  //스테이지 번호 스왑
                    answer[i] = answer[j];
                    answer[j] = tempValue;

                    tempPercent = failPercent[i]; //실패율 스왑
                    failPercent[i] = failPercent[j];
                    failPercent[j] = tempPercent;
                }
            }
            //밑에서 먼저 썼지만 이 부분을 퀵소트로 바꾸고, 2개의 배열을 쓸 것이 아니라 dictionary자료구조를 쓰면 좀 더 간단해진다.
            //다만 이제 시작한다고 생각하니까 천천히 가자.
        }
        //나는 여기서 삽입정렬을 썼는데 테스트 결과 굉장히 속도가 느리다. 나중에 퀵정렬을 다시 한번 이해해서 만들면 훨씬 빨라 질듯
        return answer;
    }
}

첫번째와 복잡도는 동일하다 다만 첫번째에서 중복 코드 그냥 썼던 걸 정리 했다. 알고리즘을 더 빠르게 만드려면 퀵소트 등 복잡도가 logN에 수렴하는 정렬을 쓰면 된다. 그래서 라이브러리에 있는 거 쓰려고 했는데 숨겨둔건지 내가 못 찾는 건지 c++처럼 stl이 java는 잘 안나와서 일단은 이대로 마무리했다.

…진짜 오래만에 코드 보고 알고리즘 보고 하는 거라서 Lv1짜리도 시간이 꽤 걸렸다. 역시 사람은 안하면 다 까먹는다. 앞으로 남은 몇개월간 빡세게 해보자. 그래보자.