[Programmars] 실패율

문제

• Programmars 42889
• 문제의 저작권은 Programmars에 있습니다.

접근방식

1.현재 스테이지에 있지만 아직 클리어하지 않은 플레이어 수를 저장한다 → int[] ing_players
2.현재 스테이지를 도달했던 총 플레이어 수를 구한다. 여기서 현재 스테이지에 있는 플레이어수+클리어했던 플레이어수를 넣어주면 된다. 따라서 클리어했던 플레이어수는 1에서 구한 ing_players의 스테이지가 큰 번호부터 내려오면서 누적합 시켜준다.
3.스테이지번호별 실패율을 구하고 리스트에 저장한다. 그리고 Comparable에 정렬 기준을 실패율 높은 순, 실패율 같으면 번호 작은 순으로 맞춰주고 정렬하면 된다.

import java.io.*;
import java.util.*;

public class Solution {
	
	static class Stage implements Comparable<Stage>{
		int num; //스테이지 번호
		double fail; //실패율
		
		public Stage(int num, double d) {
			this.num = num;
			this.fail = d;
		}

		@Override
		public int compareTo(Stage o) {
			if(this.fail == o.fail) return this.num - o.num; //실패율 같으면 번호 오름차순
			else if(this.fail < o.fail) return 1; //실패율 순 내림차순
			else return -1;
		}
	}

	public static int[] solution(int N, int[] stages) {
		int[] answer = new int[N];
		int[] ing_players = new int[N+2]; //현재 스테이지에 진행중이지만 아직 클리어하지 못한 플레이어의 수
		for(int i=0; i<stages.length; i++) {
			ing_players[stages[i]]++;
		}
		
		
		int[] total_players = new int[N+1];//스테이지에 도달한 총 플레이어 수
		int cnt = ing_players[N+1]; //바로 다음 단계에서 N번째를 클리어한 사람 수
		for(int i=N; i>=1; i--) {
			total_players[i] = ing_players[i] + cnt;
			cnt = total_players[i];
		}
		
		//실패율 구해서 리스트에 저장
		List<Stage> list = new ArrayList<>();
		for(int i=1; i<=N; i++) {
			//현재 스테이지에 도달한 플레이어가 없으면 실패율 0
			if(ing_players[i] == 0) list.add(new Stage(i, 0));
			else {
				list.add(new Stage(i, (double) ing_players[i] / total_players[i]));
			}
		}
		
		Collections.sort(list);
		
		for(int i=0; i<N; i++) {
			answer[i] = list.get(i).num;
		}
		
		return answer;
	}
}