문제 링크

내 코드

처음에 그냥 분모만 보면 안 되나? 라고 생각했는데요..

GPT - 반례.

아래와 같은 간단한 예를 들어보겠습니다.

반례 시나리오:

클래스가 2개 있다고 가정합시다.

• 클래스 A: 통과생 p=2명, 총원 t=4명 (초기 비율: 2/4 = 0.5)
• 클래스 B: 통과생 p=1명, 총원 t=2명 (초기 비율: 1/2 = 0.5)

그리고 추가로 넣을 수 있는 학생 수 K=2라고 하겠습니다. (추가되는 학생은 모두 통과한다고 가정)

전략: “항상 분모(총원)가 가장 작은 반에 추가”를 따른 경우

1. 처음에는 클래스 B의 분모 t=2가 가장 작습니다.
   클래스 B에 1명 추가:

   • 클래스 B: (1+1)/(2+1) = 2/3 ≈ 0.6667
     클래스 A는 여전히 2/4=0.5
     평균 비율: (0.5 + 0.6667)/2 ≈ 0.5833

2. 이제 클래스 B의 분모는 3, 클래스 A는 4이므로 여전히 클래스 B(분모=3)가 더 작습니다.
   다시 클래스 B에 1명 추가:

   • 클래스 B: (2+1)/(3+1)=3/4=0.75
     클래스 A=0.5
     평균 비율: (0.5+0.75)/2=1.25/2=0.625

최종 평균: 0.625

대조: 두 번째 학생은 분모가 더 크지만 클래스 A에 배치

1단계까지는 동일하므로 상태는 다음과 같습니다:

• 클래스 A: 0.5
• 클래스 B: 2/3 ≈0.6667
• 평균: ≈0.5833

이제 두 번째 학생을 클래스 A(분모=4)에 추가해보겠습니다.

• 클래스 A에 1명 추가: (2+1)/(4+1) = 3/5=0.6
• 클래스 B는 그대로 2/3=0.6667

새 평균: (0.6+0.6667)/2 = 1.2667/2 ≈ 0.6333

0.6333은 앞서 “항상 분모가 가장 작은 클래스를 선택” 전략을 사용했을 때의 최종 평균 0.625보다 더 큽니다. 즉, 단순히 분모가 가장 작은 클래스를 우선하는 로직은 최적해를 보장하지 못하는 반례가 존재함을 보여줍니다.

Solution

Approach 1: Brute Force (Time Limit Exceeded Error)

• TLE
• Complexity
  • Let $n$ be the number of classes in the classes array and $k$ be the number of extra students.
  • Time Complexity: $O(k \cdot n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        vector<double> passRatios;

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

        while (extraStudents--) {
            vector<double> updatedRatios;

            // Calculate updated pass ratios if an extra student is added
            for (int classIndex = 0; classIndex < classes.size();
                 classIndex++) {
                double newRatio = (classes[classIndex][0] + 1) /
                                  (double)(classes[classIndex][1] + 1);
                updatedRatios.push_back(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[classIndex] - passRatios[classIndex];
                if (gain > maximumGain) {
                    bestClassIndex = classIndex;
                    maximumGain = gain;
                }
            }

            // Update the selected class
            passRatios[bestClassIndex] = updatedRatios[bestClassIndex];
            classes[bestClassIndex][0]++;
            classes[bestClassIndex][1]++;
        }

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

        return totalPassRatio / classes.size();
    }
};

GPT

이 코드는 LeetCode “Maximum Average Pass Ratio” 문제를 해결하려는 단순 구현 예시로 보입니다. 문제의 핵심 아이디어는 다음과 같습니다:

• 클래스마다 현재 통과 학생 수와 총 학생 수가 주어집니다.
• extraStudents명의 추가 학생을 할당하여 전체 클래스 평균 통과율을 최대화하고자 합니다.
• 각 클래스에 한 명씩 학생을 추가할 때마다 통과율이 변화합니다.
• 이 코드에서는 매번 어떤 클래스에 학생을 추가했을 때 통과율이 가장 많이 증가하는지 조사하여, 그 클래스를 선택하고 학생을 할당하는 전략을 사용하고 있습니다.

구체적 동작 과정:

1. 초기 통과율 계산:

   vector<double> passRatios;
   for (int classIndex = 0; classIndex < classes.size(); classIndex++) {
       double initialRatio = classes[classIndex][0] / (double)classes[classIndex][1];
       passRatios.push_back(initialRatio);
   }

   각 클래스의 현재 통과율(= 통과 학생 수 / 총 학생 수)을 계산하여 passRatios 벡터에 저장합니다.

2. 추가 학생 배치 루프:

   while (extraStudents--) {
       // 각 클래스를 대상으로 학생 1명 추가 시의 새로운 통과율(newRatio)을 계산
       vector<double> updatedRatios;
       for (int classIndex = 0; classIndex < classes.size(); classIndex++) {
           double newRatio = (classes[classIndex][0] + 1) / (double)(classes[classIndex][1] + 1);
           updatedRatios.push_back(newRatio);
       }
   
       // 어떤 클래스에 넣을 때 통과율 증가가 가장 큰지 찾기
       int bestClassIndex = 0;
       double maximumGain = 0;
       for (int classIndex = 0; classIndex < updatedRatios.size(); classIndex++) {
           double gain = updatedRatios[classIndex] - passRatios[classIndex];
           if (gain > maximumGain) {
               bestClassIndex = classIndex;
               maximumGain = gain;
           }
       }
   
       // 가장 이득이 큰 클래스에 학생 1명 추가하고, 통과율 갱신
       passRatios[bestClassIndex] = updatedRatios[bestClassIndex];
       classes[bestClassIndex][0]++; // 통과 학생 수 증가
       classes[bestClassIndex][1]++; // 총 학생 수 증가
   }

   이 부분이 이 코드의 핵심:

   • 추가 학생 수가 남아 있는 동안, 매번 모든 클래스를 탐색합니다.
   • 각각의 클래스에 1명 더 넣었을 때의 새로운 통과율을 updatedRatios에 계산합니다.
   • 현재 통과율 대비 얼마나 개선되는지(gain)를 계산하여 최대 개선치를 갖는 클래스를 찾습니다.
   • 해당 클래스에 학생을 할당하고, passRatios와 classes 정보(통과/총 학생 수)를 갱신합니다.

   이 방식은 매번 O(number_of_classes) 연산을 수행하며, 이를 extraStudents번 반복하므로 시간 복잡도가 O(extraStudents * number_of_classes)로 상당히 비효율적일 수 있습니다. 하지만 문제의 아이디어 자체는 명확합니다.

3. 최종 평균 통과율 계산:

   double totalPassRatio = 0;
   for (double passRatio : passRatios) {
       totalPassRatio += passRatio;
   }
   
   return totalPassRatio / classes.size();

   모든 extraStudents 배치가 끝난 후, 최종적으로 각 클래스의 통과율을 합산한 뒤 클래스 개수로 나누어 평균 통과율을 반환합니다.

정리:

• 이 코드는 추가 학생을 하나씩 할당할 때마다 전체 클래스를 탐색하여 가장 큰 이득을 주는 클래스를 선택하는 단순한(그러나 비효율적인) 방법을 사용하고 있습니다.
• 실제 문제의 효율적인 해법은 우선순위 큐(최대힙)를 사용하여 매번 가장 이득이 큰 클래스를 O(log n)에 찾는 전략을 사용하는데, 이 코드는 그러한 최적화를 생략한 형태입니다.
• 최종 반환값은 모든 클래스를 고려한 평균 통과율입니다.

Approach 2: Priority Queue

• 324ms, 97.94MB
• Complexity
  • Let $n$ be the number of classes in the classes array and $k$ be the number of extra students.
  • Time Complexity: $O(n \log n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        // Lambda to calculate the gain of adding an extra student
        auto calculateGain = [](int passes, int totalStudents) {
            return (double)(passes + 1) / (totalStudents + 1) -
                   (double)passes / totalStudents;
        };

        // Max heap to store (-gain, passes, totalStudents)
        priority_queue<pair<double, pair<int, int>>> maxHeap;
        for (const auto& singleClass : classes) {
            maxHeap.push({calculateGain(singleClass[0], singleClass[1]),
                          {singleClass[0], singleClass[1]}});
        }

        // Distribute extra students
        while (extraStudents--) {
            auto [currentGain, classInfo] = maxHeap.top();
            maxHeap.pop();
            int passes = classInfo.first;
            int totalStudents = classInfo.second;
            maxHeap.push({calculateGain(passes + 1, totalStudents + 1),
                          {passes + 1, totalStudents + 1}});
        }

        // Calculate the final average pass ratio
        double totalPassRatio = 0;
        while (!maxHeap.empty()) {
            auto [_, classInfo] = maxHeap.top();
            maxHeap.pop();
            totalPassRatio += (double)classInfo.first / classInfo.second;
        }

        return totalPassRatio / classes.size();
    }
};

GPT

이 코드는 LeetCode “Maximum Average Pass Ratio” 문제를 해결하기 위한 우선순위 큐(힙) 기반의 효율적인 접근 방식을 보여줍니다.

문제 핵심:

• 각 클래스에 대해 현재 “통과(pass)한 학생 수”와 “총 학생 수”가 주어집니다.
• extraStudents 명의 추가 학생을 적절히 분배하여 전체 클래스들의 평균 통과율을 최대화하는 것이 목표입니다.
• 한 명의 학생을 추가할 때, 해당 클래스의 통과율(통과 학생 수 / 총 학생 수)이 어떻게 변하는지를 분석한 뒤, 가장 “통과율 개선 효과”가 큰 클래스에 학생을 배정하는 전략이 최적입니다.

접근 아이디어:

• 매번 모든 클래스를 확인하는 대신, 현재 추가 가능한 학생 한 명으로 얻을 수 있는 “통과율 증가값(gain)“을 최대 힙에 저장합니다.
• 힙에서 통과율 개선 폭이 가장 큰 클래스를 빠르게 선택하여 학생을 할당하고, 할당 후 해당 클래스의 새로운 개선 폭을 다시 힙에 넣는 과정을 반복합니다.

코드 상세 설명:

1. gain 계산 람다 함수:

   auto calculateGain = [](int passes, int totalStudents) {
       return (double)(passes + 1) / (totalStudents + 1) - (double)passes / totalStudents;
   };

   • 현재 passes/totalStudents 상태에서 한 명을 더할 경우, (passes + 1)/(totalStudents + 1)가 새 통과율이 됩니다.
   • 두 통과율의 차이가 바로 한 명을 추가했을 때의 “개선 정도(gain)“입니다.

2. 초기 힙 구성:

   priority_queue<pair<double, pair<int, int>>> maxHeap;
   for (const auto& singleClass : classes) {
       maxHeap.push({calculateGain(singleClass[0], singleClass[1]),
                     {singleClass[0], singleClass[1]}});
   }

   • 각 클래스에 대해 현재 상태에서 학생을 1명 추가했을 때 얻을 수 있는 개선량을 계산.
   • (개선량, (통과 학생 수, 총 학생 수))를 힙에 삽입.
   • 이 힙은 개선량을 키로 하는 최대 힙이므로, top()은 항상 현재 가장 많은 개선을 줄 수 있는 클래스를 가리키게 됩니다.

3. extraStudents 분배:

   while (extraStudents--) {
       auto [currentGain, classInfo] = maxHeap.top();
       maxHeap.pop();
       int passes = classInfo.first;
       int totalStudents = classInfo.second;
   
       // 해당 클래스에 학생 1명 추가
       passes += 1;
       totalStudents += 1;
       
       // 새로 갱신된 클래스 상태로 새로운 gain 계산하여 힙에 다시 push
       maxHeap.push({calculateGain(passes, totalStudents), {passes, totalStudents}});
   }

   • 남은 추가 학생 수(extraStudents)만큼 반복:
     • 힙에서 개선량이 가장 큰 클래스를 pop.
     • 이 클래스에 학생을 1명 추가 후, 클래스의 (passes, totalStudents) 갱신.
     • 갱신된 상태에서 다시 gain을 계산해 힙에 push.

   이 과정으로 매번 가장 효율적인 배분을 수행하게 됩니다.

4. 최종 평균 통과율 계산:

   double totalPassRatio = 0;
   while (!maxHeap.empty()) {
       auto [_, classInfo] = maxHeap.top();
       maxHeap.pop();
       totalPassRatio += (double)classInfo.first / classInfo.second;
   }
   
   return totalPassRatio / classes.size();

   • 모든 extraStudents를 할당한 뒤, 힙에 남아 있는 각 클래스의 (passes, totalStudents)를 이용해 최종 통과율을 합산.
   • 평균을 내어 결과 반환.

복잡도:

• n개 클래스와 extraStudents = k일 때, 매 번 할당 시 O(log n) 시간(힙 연산)으로 처리.
• 전체 시간 복잡도: O((n + k) log n) 정도 (초기 힙 구성 O(n) 포함).

정리:

• 이 코드는 우선순위 큐를 활용하여 항상 가장 효율적인 클래스에 학생을 1명씩 순차적으로 할당하는 최적화된 접근입니다.
• 덕분에 매번 모든 클래스를 순회하지 않고도 최대 평균 통과율을 효과적으로 계산할 수 있습니다.