[leetcode] 1792. Maximum Average Pass Ratio

https://leetcode.com/problems/maximum-average-pass-ratio/

초기 버전

public double maxAverageRatio(int[][] classes, int extraStudents) {
        /*
        현재 값에서 학생 수 1명 증가 시켰을때, 변동폭이 가장 큰 거 증가 
        => 학생 수 1명 감소 시키고 학생이 남았다면 증가 시킨 값으로 가서 다시 하나 증가 시켜보고 나머지 값들과 비교
        => 가장 큰 값증가 시키고, 학생이 0명 될 때까지 반복
        */
        double answer=0;
        int n = classes.length;
        double[] average = new double[n];
        double[] gap = new double[n];
        for(int i=0;i<n;i++){
            average[i] = (double) classes[i][0] / classes[i][1];
        }

        // 학생수가 없어질때까지 반복
        while(extraStudents-- != 0){
            double max = 0;
            int index = 0;

            // 변화가 가장 큰 거 찾기
            for(int i=0;i<n;i++){
                if(average[i] == 1.0) continue; // 100%면 넘어가기

                int x = classes[i][0]+1;
                int y = classes[i][1]+1;
                // System.out.println(i+":"+x+":"+y);
                gap[i] = (double) x/y - average[i];
                if(max < gap[i]){
                    max = gap[i];
                    index = i;
                }
                // System.out.println("max"+i+":"+max);
            }
            // 변화가 가장 큰 값으로 업데이트
            classes[index][0] = classes[index][0] + 1;
            classes[index][1] = classes[index][1] + 1;
            average[index] = (double) classes[index][0] / classes[index][1];
        }

        // 최종값 계산
        for(int i=0;i<n;i++){
            int x = classes[i][0];
            int y = classes[i][1];
            answer += (double) x/y;
        }
        
        return answer/n;
    }

이렇게 하면, 바뀐 값만 계산하는게 아니라 계속 전부 비교하기에 런타임 에러가 발생한다.

그렇기에 PriorityQueue 자료 구조를 활용

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        /*
        현재 값에서 학생 수 1명 증가 시켰을때, 변동폭이 가장 큰 거 증가 
        => 학생 수 1명 감소 시키고 학생이 남았다면 증가 시킨 값으로 가서 다시 하나 증가 시켜보고 나머지 값들과 비교
        => 가장 큰 값증가 시키고, 학생이 0명 될 때까지 반복
        */
        double answer=0;
        int n = classes.length;

        PriorityQueue<Grade> pq = new PriorityQueue<>(
            (a, b) -> Double.compare(b.gap, a.gap) // gap 내림차순
        );

        for(int i=0;i<n;i++){
            pq.offer( new Grade(classes[i][0], classes[i][1]) );
        }

        // 학생수가 없어질때까지 반복
        // 변화가 가장 큰 거 찾아서 업데이트
        while(extraStudents-- != 0){
            Grade max = pq.poll();
            max.update();
            pq.offer(max);
        }

        // 최종 값으로 값 구하기
        for(Grade g : pq){
            answer += (double) g.pass/g.total;
        }

		/*
        //debug
        System.out.println("debug");
        for(int i=0;i<n;i++){
            System.out.println(pq.poll().toString());
        }
        */

        return answer/n;
    }

    static class Grade{
        int pass, total;
        double gap;

        Grade(int p, int t){
            pass = p;
            total = t;
            gap = getGap(p,t);
        }

        void update(){
            pass += 1;
            total += 1;
            gap = getGap(pass,total);
        }

        static double getGap(int p, int t){
            return ( (double) (p+1)/(t+1) ) - ( (double) p/t );
        }

        // debug
        @Override
        public String toString() {
            return "pass=" + pass + ", total=" + total + ", gain=" + gap;
        }

    }
}

답안으로는 arraylist를 활용하였다.

class Solution {

    public double maxAverageRatio(int[][] classes, int extraStudents) {
        List<Double> passRatios = new ArrayList<>();

        // Calculate initial pass ratios
        for (int classIndex = 0; classIndex < classes.length; classIndex++) {
            double initialRatio =
                (double) classes[classIndex][0] / classes[classIndex][1];
            passRatios.add(initialRatio);
        }

        while (extraStudents > 0) {
            List<Double> updatedRatios = new ArrayList<>();

            // Calculate updated pass ratios if an extra student is added
            for (
                int classIndex = 0;
                classIndex < classes.length;
                classIndex++
            ) {
                double newRatio =
                    (double) (classes[classIndex][0] + 1) /
                    (classes[classIndex][1] + 1);
                updatedRatios.add(newRatio);
            }

            int bestClassIndex = 0;
            double maximumGain = 0;

            // Find the class that gains the most from an extra student
            for (
                int classIndex = 0;
                classIndex < updatedRatios.size();
                classIndex++
            ) {
                double gain =
                    updatedRatios.get(classIndex) - passRatios.get(classIndex);
                if (gain > maximumGain) {
                    bestClassIndex = classIndex;
                    maximumGain = gain;
                }
            }

            // Update the selected class
            passRatios.set(bestClassIndex, updatedRatios.get(bestClassIndex));
            classes[bestClassIndex][0]++;
            classes[bestClassIndex][1]++;

            extraStudents--;
        }

        // Calculate the total average pass ratio
        double totalPassRatio = 0;
        for (double passRatio : passRatios) {
            totalPassRatio += passRatio;
        }

        return totalPassRatio / classes.length;
    }
}