문제 바로가기

나의 풀이

이 문제는 기본적인 구현 문제이다. 다만 주의해야할 점이 몇가지 있다.

첫번째는 실패율을 구한뒤 정렬을 할때, 인덱스 값을 기억해둬야 한다는 것이다. 처음에는 for문을 두개 돌리면서 sorted된 failure 배열과 기존의 failure 배열의 값을 비교하면서 answer 배열을 채우는 것이다.

두번째는 분모에 0이 들어가지 않도록 조심해야 한다. 나의 경우 static int remain; 을 선언하고 count 값을 빼주는 식으로 했는데 for 문을 돌다보면 결국 remain이 0이 된다. 그것도 모르고 계속 double 형 배열에 count를 remain으로 나눈 값을 대입하면 0.0이 아니라 NaN 값이 들어간다.

세번째는 인덱스를 찾기 위해 for문을 돌리기보다 그냥 메모리를 조금 더 사용해서 시간 복잡도를 낮추는 것이 낫다. 그래서 배열을 쓰기보다 TreeMap에서 key는 Double, value는 List 으로 설정하면 key 값으로 자동정렬이 될테고, 0.0인 경우는 그저 리스트만 가져와주면 된다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

class Solution {

    public static int[] solution(int N, int[] stages) {
        Map<Double, List<Integer>> map = new TreeMap<>();
        double[] check = new double[N];
        int remain = stages.length;

        for (int i = 0; i < N; i++) {
            int count = 0;
            for (int j = 0; j < stages.length; j++) {
                if (stages[j] == i + 1) {
                    count++;
                }
            }
            if (count == 0) {
                if (map.containsKey(0.0)) {
                    map.get(0.0).add(i + 1);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(i + 1);
                    map.put(0.0, list);
                }
            } else {
                double key = (double) count / remain;
                if (map.containsKey(key)) {
                    map.get(key).add(i + 1);
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(i + 1);
                    map.put(key, list);
                }
                remain -= count;
            }
        }

        int[] answer = new int[N];
        int index = 0;
        List<Double> keyList = new ArrayList<>(map.keySet());
        Collections.sort(keyList, Collections.reverseOrder());
        for (int i = 0; i < keyList.size(); i++) {
            List<Integer> integers = map.get(keyList.get(i));
            for (Integer integer : integers) {
                answer[index++] = integer;
            }
        }

        for (int i : answer) {
            System.out.println("i = " + i);
        }
        return answer;
    }
}