실패율

아래는 문제 링크입니다.

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

코딩테스트 연습 - 실패율

아래는 먼저 첫 번째 풀이다.

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int [N];
        double denominator = stages.length;
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Double> result = new HashMap<>();

        for (int i = 1; i <= N +1; i++) {
            map.put(i,0);
        }
        for (int stage : stages) { //스테이지와 실패한 사람들을 넣는다.
            map.put(stage, map.getOrDefault(stage, 0) + 1);
        }

        for (Integer key : map.keySet()) {
            int person = map.get(key); //실패한 사람들
            if(denominator != 0)result.put(key, person / denominator ); //스테이지당 실패율을 넣는다.
            else result.put(key,0D);
            denominator -= person;

        }

        Set<Map.Entry<Integer, Double>> entries = result.entrySet();

        List<Map.Entry<Integer, Double>> list = new ArrayList<>(result.entrySet());
        //list.sort(Map.Entry.comparingByValue());// value에 의한 오름차순


        List<Map.Entry<Integer, Double>> collect = result.entrySet().stream()
                .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
                .collect(Collectors.toList());

        int i = 0;
        for (Map.Entry<Integer, Double> m : collect) {
            if(m.getKey() != N+1){
                answer[i++] = m.getKey();
            }
        }

        return answer;
    }
}

마지막에 정렬을 스트림을 사용해서 했는데,

뭔가 스스로 판단하기에는 코딩테스트는 효율을 중요시 여긴다고 생각해 스트림을 사용하면 안된다고 생각해서 다른 풀이를 생각해보았다.

import java.util.*;

class Solution {
    
  class Stage implements Comparable<Stage> {
        public int id;
        public double failure;

        public Stage(int id, double failure) {
            this.id = id;
            this.failure = failure;
        }

        @Override
        public int compareTo(Stage o) {
            if (failure < o.failure ) {
                return -1;
            }
            if (failure > o.failure ) {
                return 1;
            }
            return 0;
        }
    }
    
    public int[] solution(int N, int[] stages) {
        int[] answer = new int [N];
        double denominator = stages.length;
        Map<Integer, Integer> map = new HashMap<>();
        ArrayList<Stage> result = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            if(i != N + 1)map.put(i, 0);
        }

        for (int stage : stages) { //스테이지와 실패한 사람들을 넣는다.
            if(stage != N + 1) map.put(stage, map.getOrDefault(stage, 0) + 1);
        }

        for (Integer key : map.keySet()) {
            int person = map.get(key); //실패한 사람들
            if(denominator != 0) result.add(new Stage (key, person / denominator) ); //스테이지당 실패율을 넣는다.
            else result.add(new Stage (key, 0D));
            denominator -= person;
        }

        Collections.sort(result, Collections.reverseOrder());

        for(int i = 0; i < N; i++){
            answer[i] = result.get(i).id;
        }
        return answer;
    }
}

 

다른 사람들의 풀이에 들어가서 정렬에 대한 힌트를 얻었다.

처음에는 모든 스테이지를 클리어한 사람을 고려하지 않아 오류가 발생했었다.

이후 이에 대한 조건을 추가했더니 문제를 해결할 수 있었다.

자바에서 정렬 문제가 나오면 Comparable 인터페이스를 제일 떠올릴 수 있게 노력하자.