LeetCode 1792. Maximum Average Pass Ratio(JAVA)

출처 : https://leetcode.com/problems/maximum-average-pass-ratio/description/?envType=daily-question&envId=2024-12-15

 

#문제
There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [passi, totali]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.
You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.
The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.
Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10-5 of the actual answer will be accepted.
 


한 학교에는 여러 학급이 있으며 각 학급은 학생들로 구성되어 있고, 각 학급은 기말 시험을 치르게 됩니다. **2D 정수 배열 classes**가 주어지는데, 여기서 classes[i] = [passi, totali]는 i번째 학급에 총 totali명의 학생이 있고 그 중 passi명의 학생만 시험에 통과할 수 있음을 의미합니다.
또한 **정수 extraStudents**가 주어집니다. **extraStudents**는 뛰어난 학생들로, 이들은 어떤 학급에 배정되든 반드시 시험에 통과할 수 있습니다. 이 뛰어난 학생들을 학급에 할당하여 모든 학급의 평균 합격 비율을 최대화하고자 합니다.

조건:
합격 비율은 각 학급의 시험에 통과한 학생 수를 학급의 총 학생 수로 나눈 값입니다.즉, 합격 비율 = passi / totali평균 합격 비율은 모든 학급의 합격 비율의 합을 학급 수로 나눈 값입니다.

extraStudents명의 학생들을 적절히 배정하여 평균 합격 비율을 최대화했을 때의 값을 반환하세요.
결과는 실제 답과의 차이가 10^(-5) 이하이면 정답으로 인정됩니다.

 

접근 : Greedy, Heap(Priority Queue)

탐욕법과 우선순위큐를 활용하여 *뛰어난 학생* 을 추가했을때의 비율의 상승폭이 가장 큰 학급부터 학생을 추가하는 방식으로 문제를 해결할수있다.

 

상승폭 계산

(pass + 1.0) / (total + 1) - (double)pass / total;

 

학급 클래스 구현

class Class{
    int pass;
    int total;
    double inc;
    public Class(int[] array){
        pass = array[0];
        total = array[1];
        inc = calc();
    }
    //학생을 추가한다
    public Class add(){
        pass++;
        total++;
        inc = calc();
        return this;
    }
    //상승폭 계산
    private double calc(){
        return (pass + 1.0) / (total + 1) - (double)pass / total;
    }
}

 

우선순위 큐, Comparator 구현

PriorityQueue<Class> pq = new PriorityQueue<>(new Compare());

...

class Compare implements Comparator<Class> {
    public int compare(Class a, Class b) {
        if (a.inc < b.inc) {//b가 더 크다면
            return 1;//양수이므로 b 우선
        } else if (a.inc > b.inc) {//a가 더 크다면
            return -1;//음수이므로 a 우선
        } else {
            return 0;
        }
    }
}

기존에는 람다식 또는 익명클래스로 구현했지만 외부에서 구현하고 매개변수로 사용하는 방식이있다는걸 알게돼서 한번 사용해보았다.

 

 

전체코드

import java.util.Comparator;
import java.util.PriorityQueue;

//학급
class Class{
    int pass;
    int total;
    double inc;
    public Class(int[] array){
        pass = array[0];
        total = array[1];
        inc = calc();
    }
    public Class add(){
        pass++;
        total++;
        inc = calc();
        return this;
    }
    private double calc(){
        return (pass + 1.0) / (total + 1) - (double)pass / total;
    }
}
//비교자 구현
class Compare implements Comparator<Class> {
    public int compare(Class a, Class b) {
        if (a.inc < b.inc) {//b가 더 크다면
            return 1;//양수이므로 b 우선
        } else if (a.inc > b.inc) {//a가 더 크다면
            return -1;//음수이므로 a 우선
        } else {
            return 0;
        }
    }
}
public class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<Class> pq = new PriorityQueue<>(new Compare());
        for(int[] cl : classes){
            pq.add(new Class(cl));
        }
        Class cl;
        while(extraStudents-- > 0){
            Class poll = pq.poll();
            poll.add();
            pq.add(poll);
        }
        double sum = 0;
        while(!pq.isEmpty()){
            cl = pq.poll();
            sum += (double)cl.pass / cl.total;
        }
        return sum / classes.length;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.maxAverageRatio(new int[][]{{2,4}},4);
    }
}