[프로그래머스 / Level1] 실패율 (Java)

문제

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

코딩테스트 연습 - 실패율

 

풀이

• 실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수
• int N : 전체 스테이지 개수
• int[] stages : 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열
• => return : 실패율이 높은 스테이지부터 내림차순으로 스테이지 번호가 담긴 배열

 

1. 스테이지 n에 도달했으나 아직 클리어 못한 플레이어 수
   = 현재 멈춰있는 스테이지 번호가 n인 플레이어 수
   = stages[]에서 값이 n인 요소 개수
2. 스테이지 n에 도달한 플레이어 수
   = 현재 멈춰있는 스테이지 번호가 n보다 크거나 같은 플레이어 수
   = stages[] 에서 값이 n보다 크거나 같은 요소 개수
   (스테이지 n에 도달했으나 아직 클리어하지 못한 플레이어 수) + (스테이지 n+1에 도달했으나 아직 클리어하지 못한 플레이어 수) + (스테이이지 n+2에...)
3. stages[] 에는 N(전체 스테이지 개수)보다 큰 값이 있을 수 있음. (입출력 예 #1 참고)
   ex) 스테이지 수가 5일 경우, 사용자가 현재 멈춰있는 스테이지의 번호에 6이 있을 수 있음.
   = stages[] 요소 값이 5 : 스테이지 4까지 클리어하고, 마지막 스테이지 5를 아직 클리어하지 못한 상태. (N)
   = stages[] 요소 값이 6 : 마지막 스테이지 5까지 클리어한 상태. (N+1)
   

   

4. 각 스테이지의 실패율(스테이지에 도달했으나 아직 클리어하지 못한 수 / 스테이지에 도달한 수) 계산
5. 스테이지의 실패율을 기준으로 스테이지 번호를 내림차순 정렬

 

코드

import java.util.*;

class Solution {
public static int[] solution(int N, int[] stages) {
        HashMap<Integer, Double> map = new HashMap<>();
        
        int[] userFailCnts = new int[N+2];		//각 스테이지에 머물러있는 플레이어 수 
        int[] userTotalCnts = new int[N+1];		//각 스테이지에 도달한 플레이어 수
       
        //스테이지 별 머물러있는 플레이어 수 카운트
        for(int stage : stages) {
        	userFailCnts[stage]++;
        }
        
        //스테이지 별 도달한 플레이어 수 카운트
        userTotalCnts[N] = userFailCnts[N]+userFailCnts[N+1]; 
        for(int i = N-1; i >=1 ; i--) {
        	userTotalCnts[i] = userFailCnts[i] + userTotalCnts[i+1];
        }
        
        //스테이지 별 실패율 계산
        for(int i = 1; i < userTotalCnts.length; i++) {
        	if(userFailCnts[i] == 0 || userTotalCnts[i] == 0) {
        		map.put(i, 0.0);
        	}else {
            	map.put(i, (double)userFailCnts[i] / userTotalCnts[i]);
        	}
        }
        
        //실패율(value) 값으로 스테이지번호(key)를 내림차순 정렬
        List<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list, (o1, o2) -> Double.compare(map.get(o2), map.get(o1)));
        
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

• 각 스테이지에 머물러 있는 플레이어 수를 저장하는 배열의 크기가 N+2인 이유는 스테이지 번호가 1부터 N까지 인데, 이 스테이지 번호를 그대로 index로 사용하기 위해 userFailCnts[0]는 버리고 userFailCnts[1]~userFailCnts[6]만을 사용하기 위해서이다.
  ex) int[] userFailCnts = new int[5]; 으로 선언할 경우 => 배열 인덱스 0~4 사용 가능  //길이 부족
  int[] userFailCnts = new int[5+1]; => 배열 인덱스 0~5 사용 가능 //길이는 맞으나, stages 요소에서 -1한 인덱스에 값을 저장해야 함.
  int[] userFailCnts = new int[5+2]; => 배열 인덱스 0~6 사용 가능 //처음 인덱스 0자리는 버리고 1~6 사용
• 1~N 스테이지의 실패율만 필요하기 때문에, 각 스테이지에 도달한 플레이어 수를 저장하는 배열은 userTotalCnts[N+1]의 값을 구할 필요가 없다.
• userTotalCnts[i] 값이 0일 경우, 실패율을 계산할 때 0으로 나누게 되어 실패율이 0.0이 아니라 NaN으로 나온다. 
  이를 방지하기 위해 if조건에서 userTotalCnts[i] 값을 체크해준다.
  
  [userTotalCnts[i] 값이 0이 되는 테스트케이스]
  

  

  스테이지는 2까지 있는데, 2를 도달한 사람(userTotalCnts[2])도 도달했으나 클리어하지 못한 사람(userFailCnts[2])도 한명도 존재하지 않는다.

• HashMap<Integer, Double> 타입에 스테이지번호(key) : 실패율(value)를 저장한다.

 

HashMap value값 기준으로 정렬하기

[오름차순]

HashMap<Integer, Double> map = new HashMap<>();
...
List<Integer> list = new ArrayList<>(map.keySet());
Collections.sort(list, (o1, o2) -> Double.compare(map.get(o1), map.get(o2)));

[내림차순]

HashMap<Integer, Double> map = new HashMap<>();
...
List<Integer> list = new ArrayList<>(map.keySet());
Collections.sort(list, (o1, o2) -> Double.compare(map.get(o2), map.get(o1)));

 

Map에서 Entry를 추출한 뒤 순차적으로 key, value에 접근하기

Iterator it = map.entrySet().iterator();

while(it.hasNext()){
    Map.Entry entry = (Map.Entry)it.next();
    int value = ((Integer)entry.getValue()).intValue();
}