[java] 프로그래머스 - 실패율

문제

프로그래머스-실패율
사용자가 도전중인 스테이지 번호를 받아서 스테이지의 실패율을 구해 높은 순으로 스테이지 번호를 리턴하는 문제.

• 제한 사항
  스테이지 개수 N은 1 이상 500이하 자연수이다
  사용자의 현재 스테이지 정보를 담은 stages의 길이는 1 이상 200,000 이하다
  stages에는 1이상 N+1 이하의 자연수가 담겨있다
  실패율이 같은 스테이지가 있다면 작은 스테이지 번호를 우선으로 한다
  스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의한다

• 예시
  N : 5
  stages : [2, 1, 2, 6, 2, 4, 3, 3]

각 스테이지별 도전중인 유저 수를 묶으면 다음과 같다
1 스테이지 : 1
2 스테이지 : 3 3 스테이지 : 2
4 스테이지 : 1 5 스테이지 : 0 6 스테이지 : 1

스테이지의 수 N은 5이므로 5스테이지까지의 실패율을 구하면 된다

실패율은 도전중인 유저 수 / 도전한 유저의 수로 구할 수 있다
전체 유저 8명에서 1 스테이지를 해결하지 못한, 즉 도전중인 유저는 1명이다
1 스테이지 실패율 : 1/8
1을 통과한 유저 7명에서 2 스테이지를 해결하지 못한 유저는 3명이다
2 스테이지 실패율 : 3/7
… 각 스테이지 번호를 실패율 내림차순으로 정렬하면 [3,4,2,1,5]가 된다

풀이

우선 stages를 돌아 각 스테이지에 도전중인 유저가 몇명이 있는지 각각 합을 구한다
실패율과 스테이지번호를 같이 저장하기 위해(추후 정렬을 위해)
Stage라는 객체를 새로 만들었다

먼저 스테이지에 도달한 유저 수를 저장할 users 변수가 필요하다
초기 users는 stages의 길이와 같다

각 스테이지에 몇명의 유저들이 도전중인지 저장한 배열을 반복하면서
실패율을 구한다 (도전중인 유저수/users)
users에서 현재 스테이지의 도전중인 유저수를 빼준다

위의 예시의 값을 이용해 설명하자면,
users : 8명(초기값: stages길이)
1스테이지 도전중인 유저 수 : 1명

1스테이지의 실패율 : 1명 / users => 1 / 8
전체 유저 8명 중 1스테이지에 도전중인 1명을 제외한 7명은 1스테이지를 통과했으므로
1을 빼야 다음 스테이지에 도전했던 유저의 수를 구할 수 있다

users -= 1 users : 7명

실패율을 구하는 과정에서 문제조건이면서 DivisionZero오류를 막기 위해 users==0 이라면 0으로 처리한다

실패율과 스테이지번호를 저장한 result를 정렬한다
Comparator 참고 포스트

소스코드

import java.util.*;
class Solution {
	public int[] solution(int N, int[] stages) {
		int cnt[] = new int[N + 2]; // 각 스테이지별 도전중인 유저 수를 저장할 배열
		for (int i = 0; i < stages.length; i++) {
			cnt[stages[i]]++;
		}

		double users = stages.length; // 실패율 계산 시 형변환 안하려고 users를 double로 잡았다
		ArrayList<Stage> result = new ArrayList<>(); // 각 스테이지번호와 실패율을 저장할 List

		for (int i = 1; i < cnt.length - 1; i++) {
			if (users == 0) // 스테이지에 도달한 유저가 없는경우, 실패율은 0
				result.add(new Stage(0, i));
			else {
				result.add(new Stage(cnt[i] / users, i));
				users -= cnt[i]; // 현재 스테이지에 도전중인 유저는 다음스테이지 도달 유저 수에서 제외
			}
		}
		// 실패율의 내림차순 - 스테이지 번호 오름차순으로 정렬
		result.sort(Comparator.comparing(Stage::getRatio).reversed().thenComparingInt(Stage::getNum));

		int[] answer = new int[result.size()];
		for (int i = 0; i < answer.length; i++) {
			answer[i] = result.get(i).num;
		}
		return answer;
	}
}

class Stage {
	double ratio;
	int num;

	public Stage(double ratio, int num) {
		super();
		this.ratio = ratio;
		this.num = num;
	}

	public double getRatio() {
		return ratio;
	}

	public int getNum() {
		return num;
	}
}