(Python3) - LeetCode (Medium) : 1792. Maximum Average Pass Ratio

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

max heap을 사용해본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

정답 avg, heap pq를 선언 후 (1명이 추가될 경우 증가하는 합격율, 현재 합격율, index정보)를 하나의 tuple로 classes의 원소를 순회하며 계산해 저장합니다.

📔 풀이과정

extraStudents만큼 for loop를 수행하며, 1명 증가시 비율이 최대한 증가하는 순으로 extraStudents를 배분해줍니다. 1. python에서는 max heap이 없으므로 -형태로 tuple의 첫 번째 값을 저장하고 꺼냈을 때 -후 값을 구합니다.

 

2. classes에서 추가될 idx번째 수업에서 통과자와 전체 인원을 1씩 더해줍니다.

 

3. 현재 통과율에서 1명 추가됐으므로 expected_ratio과 cur_ratio를 갱신해줍니다.

 

4. 갱신된 정보를 다시 heap에 넣어줍니다.

 

5. classes를 순회하며 합격율을 구해 avg에 누적해 더해줍니다.

📔 정답 출력 | 반환

6째 자리에서 반올림한 avg값을 반환합니다.

---

📕 Code

📔 Python3

from heapq import heappush, heappop

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        avg = 0
        classes.sort()
        pq = []
        for idx, [passed, total] in enumerate(classes):
            cur_ratio = passed/total
            if cur_ratio == 1.0:
                continue
            expected_ratio = (passed+1)/(total+1) - cur_ratio
            heappush(pq, (-expected_ratio, cur_ratio, idx))

        for _ in range(extraStudents):
            if not pq:
                break
            expected_ratio, cur_ratio, idx = heappop(pq)
            expected_ratio = -expected_ratio
            passed, total = classes[idx][0] + 1, classes[idx][1] + 1
            classes[idx] = [passed, total]
            cur_ratio += expected_ratio
            expected_ratio = (passed+1)/(total+1) - cur_ratio
            heappush(pq, (-expected_ratio, cur_ratio, idx))

        for c in classes:
            avg += c[0] / c[1]
        return round(avg / len(classes), 5)

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.