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

 

문제

프로그래머스

 

알고리즘

누적합(Prefix Sum)

 

풀이

각 스테이지별로

[도달했으나 실패한 사람 수]와 [도달한 사람 수]를 구한다.

 

이때 도달한 사람 수는 실패한 사람 수의 누적합으로 구할 수 있다.

5 스테이지에 도달한 사람 = 5 스테이지 실패한 사람 + 6 스테이지까지 도달한 사람

4 스테이지에 도달한 사람 = 4 스테이지 실패한 사람 + 5 스테이지까지 도달한 사람

이를 수식으로 나타내면 다음과 같다.

 

arrival[5] = arrival[5] + arraval[6] = 0 + 1 = 1

arrival[4] = arrival[4] + arraval[5] = 1 + 1 = 2

arrival[3] = arrival[3] + arraval[4] = 2 + 2 = 4

 

예제 입력 1로 표현하면 다음과 같다.

누적합을 이용한 도달 인원 구하기

 

 

이를 이용해 각 스테이지 별 실패율을 구해 실패율이 높은 순, 실패율이 같다면 번호가 낮은 순으로 정렬하여 반환하면 된다.

 

 

코드

import java.util.*;

class Solution {
	public ArrayList<Integer> solution(int N, int[] stages) {
		ArrayList<Integer> answer = new ArrayList<>();
		int[] fail = new int[N + 2];
		int[] arrival = new int[N + 2];

		for (int s : stages) {
			fail[s]++;
			arrival[s]++;
		}

		for (int i = N; i >= 1; i--)
			arrival[i] += arrival[i + 1];

		ArrayList<Stage> stageList = new ArrayList<>();
		for (int i = 1; i <= N; i++) {
			if (arrival[i] == 0)
				stageList.add(new Stage(i, 0));
			else
				stageList.add(new Stage(i, fail[i] / (double) arrival[i]));
		}

		Collections.sort(stageList);

		for (Stage stage : stageList)
			answer.add(stage.num);

		return answer;
	}

	public class Stage implements Comparable<Stage> {
		int num;
		double failRatio;

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

		@Override
		public int compareTo(Stage s) {
			return failRatio == s.failRatio ? num - s.num : -Double.compare(failRatio, s.failRatio);
		}
	}
}