[프로그래머스_Level1] 실패율_2019 카카오 신입 공채

https://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 으로 정의한다.

 

[코드]

import java.util.*;

class Solution {
public int[] solution(int N, int[] stages) {
	        int[] answer=new int[N];
	        /*
	         * 각 스테이지마다 실패율을 저장하기 위해 Map을 사용한다.
	         * Map은 key 값과 value 값을 동시에 저장할 수 있는 자료구조로
	         * 후에 value 값의 크키에 따라 key 값을 정렬하기 용이하다. 
	         */
	        Map<Integer,Double> map=new HashMap<>();
	        
	        // 각 스테이지 마다 실패율을 구하는 for문 실행 
	        for(int i=1;i<=N;i++) {
	        	int stage=i; // 스테이지 변수
	        	int noclearpeople=0; // 스테이지를 클리어하지 못한 수
	        	int clearpeople=0; // 스테이지에 도달한 수
	        
	        	for(int j=0;j<stages.length;j++) {
	        		// 스테이지 값과 같으면 스테이지에 도달했으나 클리어 X
	        		if(stage==stages[j])
	        			noclearpeople++;
	        		// 스테이지 값보다 같거나 크다면 스테이지에 도달한 수
	        		if(stage<=stages[j])
	        			clearpeople++;
	        	}
	        	
	        	// 실패율 구하기 : 스테이지에 도달했으나 아직 클리어 못한 수 / 스테이지에 도달한 수
	        	double failure=0;
	        	if(noclearpeople!=0&&clearpeople!=0)
	        		failure=(double)noclearpeople/(double)clearpeople;
	        	
	        	// 각 스테이지 별로 실패율을 저장한다.
	        	map.put(stage,failure);
	        }
	        
	        // 실패율에 크기에 따라 스테이지 값을 배열에 저장한다.
	        for(int i=0;i<N;i++) {
	        	double max=-1;
	        	int maxkey=0; // key 값(=스테이지)
	        	for(Integer key:map.keySet()) {
	        		// 실패율이 가장 높은 스테이지 찾기
	        		if(max<map.get(key)) {
	        			max=map.get(key);
	        			maxkey=key;
	        		}
	        	}
	        	answer[i]=maxkey;
	        	map.remove(maxkey);
	        }
	        return answer;
	  }
}

[고찰]

 이번 문제는 스테이지에 따라 실패율을 저장할 수 있는 Map을 사용하는 것이 핵심이었다. 만약 배열을 사용하게 된다면 실패율이 큰 스테이지부터 answer 배열에 저장할때 배열의 인덱스를 사용할 수 없게되며, 실패율이 큰 스테이지 부터 정렬하는 것이 어려워진다. 이를 간단하게 만들어주는 것이 key와 value 값을 같이 저장할 수 있는 Map이다. 이 자료구조를 이용한다면 어렵지 않게 해결할 수 있는 문제였다.