실패율 문제 풀이

실패율 = 도달했으나 클리어하지 못한 유저 수/ 도달한 유저 수

아무도 도달하지 못한 경우 실패율 = 0

전체 스테이지 개수 N 

현재 유저들이 멈춰있는 스테이지 번호가 담긴 배열 stages

실패율이 높은 스테이지부터 내림차순으로 정렬하고 실패율이 같은 경우 스테이지 번호의 오름차순 정렬하여 반환

 

int[] current = new int[N+1];

for (int i = 0; i < stages.length; i++) {

for (int j = 0; j < stages[i]; j++) {

current[j]++;

}

}

각 스테이지별 현재까지 유저들이 지나가거나 멈춰있는 횟수를 담은 배열 current 

 

double[] failure = new double[N];

for (int i = 0; i < failure.length; i++) {

if(current[i]==0)failure[i]=0.0;

else failure[i] = (0.0+current[i]-current[i+1])/current[i];

}

실패율을 double[]로 저장 

만약 도달한 사람이 없다면 (current[i]==0) 실패율은 0.0 

 

Map<Double,ArrayList<Integer>> failureMapR = new HashMap<Double, ArrayList<Integer>>();

for (int i = 0; i < failure.length; i++) {

ArrayList<Integer> list = failureMapR.getOrDefault(failure[i], new ArrayList<Integer>());

list.add(i+1);

failureMapR.put(failure[i], list);

}

 

실패율을 map에 저장 

실패율을 key로 

해당 실패율에 대한 층 수는 중복될 수 있으므로 ArrayList<Integer>를 value로 갖는다. 

 

Arrays.sort(failure);

for (int i = failure.length-1; i >=0; i--) {

ArrayList<Integer> temp = failureMapR.get(failure[i]);

for (int j = 0; j < temp.size(); j++) {

answer.add(temp.get(j));

}

temp.removeAll(temp);

}

failure를 정렬하고 정렬된 배열의 뒷원소부터 map에서 찾아서 층 수를 answer에 저장해준다.