본문으로 건너뛰기

1792 - Maximum Average Pass Ratio

정보

풀이 키워드​

스포주의

자료구조 힙 그리디


풀이 코드​

정보
  • 메모리: 83900 KB
  • 시간: 292 ms
class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // 가장 ratio 낮은 class에 엘리트 넣기 -> WA
        // 가장 delta값 높은 class에 엘리트 넣기 -> AC
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
            // max-heap
            // return Double.compare(b[2], a[2]);
            if (a[2] < b[2]) return 1;
            else return -1;
        });

        for (int[] c : classes) {
            double delta = ((c[0]+1.0) / (c[1]+1.0)) - ((double)(c[0]) / c[1]);
            pq.offer(new double[]{c[0], c[1], delta});
        }

        while (extraStudents-- > 0) {
            double[] c = pq.poll();
            double np = c[0] + 1;
            double nt = c[1] + 1;
            double nd = ((np+1) / (nt+1)) - (np / nt);
            pq.offer(new double[]{np, nt, nd});
        }

        double sum = 0.0;
        Object[] arr = pq.toArray();
        for (int i = 0; i < arr.length; ++i) {
            double[] c = (double[]) arr[i];
            sum += c[0] / c[1];
        }

        // 최종 avg ratio 계산
        return sum / classes.length;
    }
}

풀이 해설​

extraStudents만큼 엘리트를 추가 배정해서 전체 class의 최대 pass ratio를 구하는 문제이다.

현재 가장 낮은 ratio의 클래스에 엘리트를 배정하면 안되고

ratio delta 값이 가장 높은 class에 배정해야 한다.

ratio delta는 (배정 전 ratio) - (배정 후 ratio) 로 구할 수 있다.


최적화 요소​

⚠️ Comparator 연산은 간단하게​

Comparator에서 delta 연산하지 말고 그냥 원소 하나 더 추가해라.

메모리 아꼈다가 중복 연산 비용으로 150ms 가량 손해본다.

comparator에서 delta 연산하는 코드
class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // 가장 ratio 낮은 class에 엘리트 넣기 -> WA
        // 가장 delta값 높은 class에 엘리트 넣기 -> AC
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
            double da = (a[0]+1)/(a[1]+1) - a[0]/a[1];
            double db = (b[0]+1)/(b[1]+1) - b[0]/b[1];
            return Double.compare(db, da); // max-heap
        });

        for (int[] c : classes) {
            pq.offer(new double[]{c[0], c[1]});
        }

        while (extraStudents-- > 0) {
            double[] c = pq.poll();
            double nc0 = c[0] + 1;
            double nc1 = c[1] + 1;
            pq.offer(new double[]{nc0, nc1});
        }

        double sum = 0.0;
        while (!pq.isEmpty()) {
            double[] c = pq.poll();
            sum += c[0] / c[1];
        }

        // 최종 avg ratio 계산
        return sum / classes.length;
    }
}

⚠️ Double.compare 딜레마​

PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
    // max-heap
    return Double.compare(b[2], a[2]);
});

단순 gt / lt 비교보다 비용이 높긴 하다.

부동소수점 오차에 민감한 경우 아니면 대충 비교해도 AC 나오는데,
일단은 Double.compare를 쓰고 시간 남으면 gt / lt로 최적화하는 방식이 좋을듯 하다.


⚠️ pq 원소 꺼내면서 합산 금지​

최적화 전 (끔찍)
double sum = 0.0;
while (!pq.isEmpty()) {
    double[] c = pq.poll();
    sum += c[0] / c[1];
}

poll하면서 합산 시 T(n log n)T(n\,log\,n) 의 비용이 추가된다. ^ㅅ^

최적화 후
double sum = 0.0;
Object[] arr = pq.toArray();
for (int i = 0; i < arr.length; ++i) {
    double[] c = (double[]) arr[i];
    sum += c[0] / c[1];
}

Object[]로 튀어나와서 캐스팅의 불편함이 있지만 최적화하면 36ms가 줄어든다.


메모​

  • PQ Comparator 연습하기 좋은 문제
  • 정렬 지표 발상이 핵심