[Python] SlidingWindow Example

# Problem Statement

You are given an integer array candies of length n and a single integer totalExtraCandies (a shared pool, not per-child). Your goal is to distribute the totalExtraCandies among any number of kids such that you maximize the number of kids who end up with the same maximum number of candies. In other words, you want to find the largest subset of kids who can all reach the same candy count X, where X is the new maximum of the entire array after distribution.

 

위의 문제를 보고 상황을 세가지를 추론해 낼 수 있다. 첫 번째로는 shared pool 즉 한정된 자원이라는 점이다. 그래서 totalExtraCandies에서 누구한테 먼저 줄 것인가? 가 코드에 반영되어야 한다고 생각이 들며, 가장 가까이 가진 아이들부터 사탕을 채워주는 게 가장 많은 아이를 포함할 수 있는 길이다. 두 번째로는 Maximize the number of kids이다. 서로 사탕 개수가 비슷한 아이들끼리 묶는 것이 예산 소모가 적기 때문에 sorting을 해서 비슷한 아이들끼리 이웃하게 만든다. 세 번째는 데이터 규모에 Constraints가 있다는 점이다.

 

문제 내에서 바로 확인할 수 있는 팁은 "가장 사탕이 많은 아이를 기준으로 나머지 아이들을 맞춘다"라는 발상 자체가 Greedy algorithm이다. "연속된 구간"이라는 점은 Sliding window 개념이고 복잡도 분석에 해당하는건 제약 사항을 보고 알고리즘을 역추적하는 능력이다.

---

#  Example Code

from typing import List

class Solution:
    def maxKidsWithSameMax(self, candies: List[int], totalExtraCandies: int) -> int:
        # 1. 먼저 정렬합니다. 사탕 개수가 비슷한 아이들을 묶어야 효율적입니다.
        candies.sort()
        
        n = len(candies)
        left = 0
        max_kids = 0
        current_window_sum = 0
        
        # 2. 슬라이딩 윈도우 탐색
        for right in range(n):
            current_window_sum += candies[right]
            
            # 현재 윈도우의 모든 아이를 가장 사탕이 많은 아이(candies[right])와 
            # 똑같이 맞추기 위해 필요한 총 사탕 개수를 계산합니다.
            window_size = right - left + 1
            needed_candies = (candies[right] * window_size) - current_window_sum
            
            # 만약 가진 사탕(totalExtraCandies)보다 많이 필요하다면, 
            # 왼쪽 포인터를 옮겨 윈도우를 줄입니다.
            while needed_candies > totalExtraCandies:
                current_window_sum -= candies[left]
                left += 1
                # 윈도우 사이즈와 필요한 사탕 개수 다시 계산
                window_size = right - left + 1
                needed_candies = (candies[right] * window_size) - current_window_sum
            
            # 최대로 모인 아이들의 수를 업데이트합니다.
            max_kids = max(max_kids, right - left + 1)
            
        return max_kids

# 테스트 케이스
sol = Solution()
print(sol.maxKidsWithSameMax([1, 4, 2, 7], 5))  # Output: 3
print(sol.maxKidsWithSameMax([1, 2, 4], 5))     # Output: 3

---