[프로그래머스] 실패율

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

전체 스테이지 개수 N과 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열이 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 정렬하여 배열을 return 하는 문제이다.

문제 이해를 위해 입출력 예 #1을 기준으로 설명하면 다음과 같다.

e.g. N = 5, stages = [2, 1, 2, 6, 2, 4, 3, 3]

1번 스테이지는 총 8명의 사용자 중 1명이 아직 통과하지 못했으므로 $1/8$

2번 스테이지는 총 8명의 사용자 중 1번 스테이지를 통과하지 못한 사람을 제외하고, 3명이 아직 통과하지 못했으므로 $3/7$

쭉쭉 계산해서 전체 스테이지 중 실패율이 가장 큰 스테이지부터 정렬하여 배열로 return 하면 되는 것이다.

여기서 한가지 떠올려야 하는 아이디어는 실패율과 스테이지를 동시에 저장할 수 있는 공간이 필요하고, 자바에서는HashMap을 사용하면 key를 스테이지, value를 실패율로 저장해야한다는 점이다.

또한 주어진 stages 배열에서 같은 스테이지에 멈춰 있는 사용자가 몇 명이 파악하기 위해 이를 카운팅하는 배열이 필요하다.

배열에서 같은 요소가 몇개 있는지 파악하는 방법은 여러가지가 있겠지만, 계수 정렬 알고리즘을 활용하면 비교적 쉽게 해결할 수 있다.

바로 주어진 배열의 요소를 새로운 배열의 인덱스로 활용하여 값을 카운팅하는 것이다.

코드에서는 challenger 배열이 그 역할을 하고 있다.

마지막으로 HashMap에 저장된 실패율을 배열로 다시 return 해야 하므로 스트림을 통해 처리하는 과정이 필요하다.

entrySet()은 HashMap의 모든 key-value를 Set형태로 가져온다. (1, 0.5)와 같이 하나의 묶음으로 들고오는 것이다.

이를 stream() 함수를 통해 스트림으로 변환한다.

sorted() 함수를 통해 정렬을 진행해야 하는데, 람다식을 통해 보다 간결하게 코드를 작성할 수 있다.

getValue()를 통해 HashMap의 value 값인 실패율을 들고와 비교한다. 앞의 값이 크면 1을, 같으면 0을, 작으면 -1을 반환한다.

여기서 o2와 o1의 위치를 바꿔서 전달하므로, 값이 큰 순서대로 내림차순되어 정렬된다.

mapToInt(HashMap.Entry::getKey)는 정렬된 HashMap의 Entry에서 key에 해당하는 스테이지 번호만을 추출하여 IntStream으로 반환한다.

toArray()를 통해 배열로 최종 return한다.

따라서 문제풀이 코드는 다음과 같다.

import java.util.HashMap;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] challenger = new int[N + 2];
        for (int i = 0; i < stages.length; i++) {
            challenger[stages[i]] += 1;
        }
        
        HashMap<Integer, Double> fails = new HashMap<>();
        double total = stages.length;
        
        for (int i = 1; i <= N; i++) {
            if (challenger[i] == 0) {
                fails.put(i, 0.);
            } else {
                fails.put(i, challenger[i] / total);
                total -= challenger[i];
            }
        }
        
        return fails.entrySet().stream()
            .sorted((o1, o2) -> Double.compare(o2.getValue(), o1.getValue()))
            .mapToInt(HashMap.Entry::getKey).toArray();
    }
}

추가로 만약 스트림 기법이 익숙하지 않다면 아래처럼 익명 클래스와 오버라이딩 기법을 합쳐서 구현해도 되지만, 코드가 더 길어지니 스트림에 익숙해지면 좋다.

import java.util.HashMap;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] challenger = new int[N + 2];
        for (int i = 0; i < stages.length; i++) {
            challenger[stages[i]] += 1;
        }
        
        HashMap<Integer, Double> fails = new HashMap<>();
        double total = stages.length;
        
        for (int i = 1; i <= N; i++) {
            if (challenger[i] == 0) {
                fails.put(i, 0.);
            } else {
                fails.put(i, challenger[i] / total);
                total -= challenger[i];
            }
        }
        
        // 엔트리 셋을 리스트로 변환
        List<Map.Entry<Integer, Double>> entryList = new ArrayList<>(fails.entrySet());

        System.out.println(entryList);

        // Comparator 구현
        Comparator<Map.Entry<Integer, Double>> comparator = new Comparator<Map.Entry<Integer, Double>>() {
            @Override
            public int compare(Map.Entry<Integer, Double> o1, Map.Entry<Integer, Double> o2) {
                int compare = Double.compare(o2.getValue(), o1.getValue());
                if (compare != 0) {
                    return compare; // 실패율이 다르면 내림차순 정렬
                } else {
                    return Integer.compare(o1.getKey(), o2.getKey()); // 실패율이 같으면 스테이지 번호 오름차순
                }
            }
        };

        // 리스트 정렬
        Collections.sort(entryList, comparator);

        // 결과 배열 생성
        int[] answer = new int[N];
        for (int i = 0; i < entryList.size(); i++) {
            answer[i] = entryList.get(i).getKey();
        }

        return answer;
    }
}