[프로그래머스][2019 KAKAO BLIND RECRUITMENT] 실패율 (level 1)

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

코딩테스트 연습 - 실패율 | 프로그래머스

 

방법 1 : Map, List, Entry 활용

import java.util.*;
import java.util.Map.Entry;
 
class Solution {
    public int[] solution(int N, int[] stages) {
 
        int[] arrFailure = new int[N];
        int iTotal = stages.length;
 
        // 오름차순 정렬
        Arrays.sort(stages);
 
        // 실패횟수 구하기
        for (int i = 0; i < stages.length; i++) {
 
            if (stages[i] > N) {
                continue;
            }
            arrFailure[stages[i] - 1]++;
        }
 
        // 인덱스-실패율 맵 선언
        Map<Integer, Double> map = new HashMap<Integer, Double>();
 
        // 실패율 구하기  (total : 시도 횟수)
        for (int i = 0; i < N; i++) {
            
            double dRatio = (iTotal == 0) ? 0 : arrFailure[i] / (double) iTotal;
            map.put(i + 1, dRatio);
            iTotal -= arrFailure[i];
            //System.out.println(map.get(i + 1));
        }
 
        // 순서 유지를 위해 링크드 리스트
        List<Map.Entry<Integer, Double>> list = new LinkedList<>(map.entrySet());
 
        // value기준 내림차순, 인덱스 기준 오름차순 정렬
        Collections.sort(list, new Comparator<Map.Entry<Integer, Double>>() {
 
            @Override
            public int compare(Entry<Integer, Double> o1, Entry<Integer, Double> o2) {
 
                if (o2.getValue() - o1.getValue() > 0) {
                    return 1;
                }
 
                if (o2.getValue() - o1.getValue() < 0) {
                    return -1;
                }
 
                return o1.getKey() - o2.getKey();
            }
        });
 
        int[] answer = new int[N];
        int i = 0;
        
        // 배열에 순서대로 인덱스 담기
        for (Iterator<Map.Entry<Integer, Double>> iter = list.iterator(); iter.hasNext();) {
            Map.Entry<Integer, Double> entry = iter.next();
            answer[i++] = entry.getKey();
        }
 
        return answer;
    }
}

 

방법 2 : 배열 활용

import java.util.Arrays;
import java.util.Comparator;
 
class Solution {
    public int[] solution(int N, int[] stages) {
 
        int[] arrFailure = new int[N];
        int iTotal = stages.length;
 
        // 오름차순 정렬
        Arrays.sort(stages);
 
        // 실패횟수 구하기
        for (int i = 0; i < stages.length; i++) {
 
            if (stages[i] > N) {
                continue;
            }
            arrFailure[stages[i] - 1]++;
        }
        
        // 인덱스-실패율 담을 배열 선언 ( '/'로 구분 )
        String[] arrMap = new String[N];
        
        // 실패율 구하기  (total : 시도 횟수)
        for (int i = 0; i < N; i++) {
            
            double dRatio = (iTotal == 0) ? 0 : arrFailure[i] / (double) iTotal;
            arrMap[i] = (i + 1) + "/" + dRatio;
            iTotal -= arrFailure[i];
        }
 
        // 실패율 기준 내림차순, 인덱스 기준 오름차순 정렬
        Arrays.sort(arrMap, new Comparator<String>() {
 
            @Override
            public int compare(String o1, String o2) {
 
                double order = Double.parseDouble(o2.split("/")[1]) - Double.parseDouble(o1.split("/")[1]);
 
                if (order > 0) {
                    return 1;
                }
                if (order < 0) {
                    return -1;
                }
 
                return Integer.parseInt(o1.split("/")[0]) - Integer.parseInt(o2.split("/")[0]);
            }
        });
 
        int[] answer = new int[N];
 
        // 배열에 순서대로 인덱스 담기
        for (int i = 0; i < arrMap.length; i++) {
            answer[i] = Integer.parseInt(arrMap[i].split("/")[0]);
        }
 
        return answer;
    }
}

 

 

방법 1이 방법 2보다 2배 이상 빠르다!

 

Collection.sort()와 Arrays.sort(), 그리고 new Comparator를 활용하였다. 

구조체에 따라 적절한 정렬 방식을 선택하면 된다.

방법1이 방법2보다 빠른건 아마...

Entry를 정렬하는 것이 배열을 정렬하는 것보다 빠르기 때문이 아닐까??

 

 

TIP

new Comparator는 오름차순이 기본이다. 

오름차순 정렬일때, o1, o2의 대소관계와 return값의 상관관계는 다음과 같다. 

대소관계	compare()의 return 값
o1 > o2	양수
o1 = o2	0
o1 < o2	음수

 

내림차순 정렬을 하고 싶으면 이와 반대로 하면 된다. 

 

 

 

처음에 o1.compareTo(o2) 로 계속 해서 틀렸다...

수 비교와 문자열 비교는 엄연히 다름!!