[프로그래머스/42889/JAVA] 실패율

Kakao Blind Recruitment 2019

날짜	분류	번호	알고리즘 분류
21-03-31	프로그래머스	42889	구현?	링크

문제 요약

1. 각 스테이지의 실패율을 구하여 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호를 정렬하여 반환
2. 실패율 = 도달했지만 클리어X인 사람 / 도달한 사람

 

풀이

1. 각 스테이지에 머물러 있는 사람의 숫자를 구함
2. 스테이지1부터 머물러있는 사람/도달한 사람(=실패율) 계산
   • 도달한 사람 = 전체 - 이전단계에 머물러 있는 사람
3. 실패율과 스테이지의 번호를 담고 있는 Node객체를 pq에 넣어 정렬
4. pq에서 하나씩 빼면서 정답 배열에 넣음

 

비고

• 휴.... 내일은 레벨 3으로 풀어야지...

 

 

package KakaoBlindRecruitment2019.P42889_실패율;

import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

	static public int[] solution(int N, int[] stages) {
		int[] answer = new int[N];

		int tot = stages.length;
		for (int i = 0; i < tot; i++) {
			if (stages[i] > N)
				continue;
			answer[stages[i] - 1]++;
		}

		double clear = tot;
		Queue<Node> pq = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			if (clear == 0) {
				pq.add(new Node(i + 1, 0));
				continue;
			}
			pq.add(new Node(i + 1, answer[i] / clear));
			clear -= answer[i];
		}

		for (int i = 0; i < N; i++) {
			answer[i] = pq.poll().no;
		}

		return answer;
	}

	static class Node implements Comparable<Node> {
		int no;
		double fail;

		public Node(int no, double fail) {
			this.no = no;
			this.fail = fail;
		}

		@Override
		public int compareTo(Node o) {
			if (this.fail == o.fail)
				return this.no - o.no;
			return -Double.compare(this.fail, o.fail);
		}

	}

	public static void main(String[] args) {
//		int[] result = solution(5, new int[] { 2, 1, 2, 6, 2, 4, 3, 3 });
//		int[] result = solution(7, new int[] { 2, 1, 2, 6, 2, 4, 3, 3 });
		int[] result = solution(4, new int[] { 4, 4, 4, 4, 4 });
		for (int i : result)
			System.out.print(i + " ");
	}

}