[2019 KAKAO BLIND RECRUITMENT] 실패율.java

📖 문제

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

실패율

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

• 실패율은 다음과 같이 정의한다.
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

---

🔑 풀이

1. 각 스테이지 별로 통과하지 못한 유저 수를 trying 배열에 저장

2. 각 스테이지 별로 실패율을 구해 HashMap<스테이지,실패율>로 저장

   ** 실패율 구하는 법

   스테이지 1: 1을 통과하지 못한 사람 / stages 길이

   스테이지 1 이후: 해당 스테이지를 통과하지 못한 사람 / ( 앞 스테이지를 시도한 사람 - 앞 스테이지를 통과하지 못한 사람)

3. hm을 내림차순 정렬

4. answer에 옮기기

import java.util.*;
import java.util.stream.Collectors;

class Solution {
	public static int[] solution(int N, int[] stages) {
		int[] answer = new int[N];
		float[] trying = new float[N]; // 스테이지를 통과하지 못한 사용자 수

		// 각 스테이지를 시도하고 있는 유저 수 구하기
		for (int stage : stages) {
			if (stage <= N)
				trying[stage - 1]++;
		}

		// 스테이지 별 실패율 저장
		// 실패율 = 현재 스테이지를 통과하지 못한 인원 / ( 앞 스테이지를 도전한 인원 - 앞 스테이지를 통과하지 못한 인원 )
		int length = stages.length;
		HashMap<Integer, Float> failure = new HashMap<>();
		for (int i = 0; i < N; i++) {
			if (i == 0) { // 스테이지 1: 모든 사람이 참여함. 분모==stages.length
				failure.put(i + 1, trying[i] / length);
			} else { // 스테이지 1 이후 
				if (length - trying[i - 1] == 0) // 스테이지에 도달한 사람이 없는 경우
					failure.put(i + 1, 0f); // 실패율=0
				else
					failure.put(i + 1, trying[i] / (length - trying[i - 1]));
				length -= trying[i - 1];
			}
		}

		// 실패율 내림차순 정렬 
		List<Map.Entry<Integer, Float>> entries = failure.entrySet().stream()
				.sorted(Map.Entry
                .comparingByValue(Comparator.reverseOrder()))
                .collect(Collectors.toList());
        
        // answer에 hm 순으로 스테이지 저장
		int i = 0;
		for (Map.Entry<Integer, Float> entry : entries) {
			answer[i] = entry.getKey();
			i++;
		}
		return answer;
	}
}