1. 문제 소개

2141. Maximum Running Time of N Computers

2. 나의 풀이

이진 탐색(Binary Search)을 힌트를 사용해 문제를 풀었다.
시간복잡도는 S=sum(batteries) // n일 때 $O(n\, log S)$이다.

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        ub = sum(batteries) // n          # 가능한 최대 상한: 총 배터리량/n
        lb = min(batteries)               # 가능한 최소 하한(0으로 잡아도 무방)

        while lb <= ub:
            mid = (lb + ub) // 2          # 현재 후보 실행 시간(mid)
            total = 0

            for b in batteries:
                total += min(b, mid)      # 각 배터리는 최대 mid까지 기여 가능

            if total >= n * mid:          # mid시간 동안 n대를 켤 수 있으면
                ans = mid                 # mid는 유효한 실행 시간
                lb = mid + 1              # 더 긴 시간이 가능한지 오른쪽 탐색
            else:
                ub = mid - 1              # mid 불가능 → 더 짧은 쪽으로 이동
        
        return ans                        # 가능한 최대 실행 시간

3. 다른 풀이

아래 코드는 Greedy Search를 적용한 방법이다.
이는 "큰 것부터 제거하면 항상 정답에 더 가까워지는 구조"이기 때문이다.

class Solution:
    def maxRunTime(self, n: int, arr: List[int]) -> int:
        arr.sort()                      # 배터리를 용량 기준으로 오름차순 정렬

        total = sum(arr)                # 전체 배터리 용량의 합

        # 가장 큰 배터리(arr[-1])가 "평균적으로 가능한 최대 시간(total // n)"보다 크면
        # → 이 배터리는 혼자 과도하게 커서 전체 n대를 위한 균형 배분이 불가능함
        # → 해당 배터리를 하나 제거(arr.pop())하고 n도 1 감소시킴
        # → 즉, "너무 큰 배터리"를 먼저 제외하며 균형 가능한 집합을 만든다
        while arr[-1] > total // n:
            n -= 1                      # 컴퓨터 1대를 제외 (큰 배터리가 혼자 독식하기 때문)
            total -= arr.pop()          # 가장 큰 배터리를 제외하고 총합 갱신

        # 이제 남아 있는 배터리들의 총합을 남은 n대로 균등하게 분배할 수 있으며,
        # total // n이 바로 가능한 최대 실행 시간
        return total // n

4. 마무리

오랜만에 본 이진탐색과 그리디 알고리즘이라 문제를 푸는 데 애를 먹었다.