[Leetcode/Sliding Window] 1176. Diet Plan Performance

// calories = [1,2,3,4,5]
// k = 2
// lower = 5
// upper = 6

// 1st: (1,2) = 3 < lower -> -1
// 2nd: (2,3) = 5 -> 0

슬라이딩 윈도우 접근법:

• 슬라이딩 윈도우를 사용하면 매번 k 길이의 구간을 합산하는 대신, 윈도우를 한 칸씩 이동하며 기존 합에서 가장 왼쪽 값을 빼고, 새롭게 들어온 값을 더하는 방식으로 효율적으로 합계를 구할 수 있다.
• 시간 복잡도는 O(n)으로, calories 길이가 최대 10^5까지 가능하므로 효율적으로 동작한다.

class Solution:
	def dietPlanPerformance(self, calories: List[int], k: int, lower:int, upper: int) -> int:
    	points = 0
        window_sum = sum(calories[:k])
        
        # 첫번째 윈도우의 점수 계산
        if window_sum < lower:
        	points -= 1
        elif window_sum > upper:
        	points += 1
            
        # 슬라이딩 윈도우를 이용하여 나머지 구간 확인
        for i in range(k, len(calories)):
        	window_sum += calories[i] - calories[i-k] # 윈도우 이동
            if window_sum < lowewr:
            	points -= 1
            elif window_sum > upper:
            	points += 1
        return points

🔹 설명

1. window_sum을 이용해 첫 k일간의 총합을 구한다.
2. window_sum을 lower 및 upper와 비교하여 점수를 갱신한다.
3. 이후, for 루프를 사용해 슬라이딩 윈도우 방식으로 window_sum을 갱신한다.
   • 새롭게 추가된 calories[i]를 더하고, 가장 왼쪽 calories[i-k]를 제거한다.
   • 이후 점수를 다시 업데이트한다.
4. 최종 점수를 반환한다.

🔹 시간 복잡도 분석

• O(k) 연산이 첫 k일 합을 구하는 데 사용된다.
• 이후 O(n-k)의 반복문이 O(1) 연산으로 window_sum을 갱신한다.
• 전체 시간 복잡도: O(n)