[프로그래머스] 2019 카카오 블라인드 #2 실패율 (Java)

#2 실패율

난이도 : LEVEL 1
유형 : 자료구조

코딩테스트 연습 - 실패율

▸ 문제

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.
이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

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

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

▸ 입력

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

 

문제 풀이

값의 변화를 잘 잡아줘서 매 스테이지마다 남은 인원수와 실패한 인원수를 구해주면 된다. 잠깐 헤맸던 부분은 문제를 제대로 읽지 않아 stages의 범위가 1~n+1인 부분을 고려하지 않았었다. 마지막 스테이지까지 클리어 한 인원은 굳이 셈을 해주지 않아도 된다. 항상 카카오 기출을 풀때마다 설계의 중요성을 느끼게 해준다.

설계

• 1~n번 스테이지까지 각 인원이 몇 명인지 카운트 해준다.
• 1~n번 스테이지까지 탐색하여 실패율을 조사한다.
  • 현재 i번 스테이지에 남은 인원이 0명이면 실패율 0을 저장해준다.
  • 실패율 = (현재 stage에 속한 인원 수 / 남은 전체 인원 수)을 카운트 해준다.
    • 카운트한 후 이번에 셈한 인원들은 전체 인원 수에서 제외시킨다. 남은 전체 인원 수 -= 현재 stage에 속한 인원 수
• 실패율을 모두 구했으면 내림차순으로 정렬하여 실패율이 높은 순대로 출력해준다.

 

풀이 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int[] solution(int n, int[] stages) {
		int[] stageStatus = new int[n+1];
		for(int num : stages) {
			if(num == n+1) continue;
			stageStatus[num]++;
		}
		
		Map<Integer, Double> res = new HashMap<>();
		int total = stages.length;
		for(int i=1; i<n+1; i++) {
			if(total==0) {
				res.put(i, (double)0);
			}
			else {
				double rate = (double)stageStatus[i]/(double)total;
				total-=stageStatus[i];
				res.put(i, rate);
			}
		}
		
		List<Integer> list = new ArrayList<>(res.keySet());
		Collections.sort(list, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return Double.compare(res.get(o2), res.get(o1));
			}
		});
		
		int[] answer = new int[n];
		for(int i=0; i<n; i++) {
			answer[i] = list.get(i);
		}
		return answer;
    }
}