문제 개요
다이어터가 i번째 날에 섭취한 칼로리를 calories[i]라고 합시다. 정수 k가 주어졌을 때, 연속된 k일 구간(calories[i], calories[i+1], ..., calories[i+k-1], 단 0 <= i <= n-k)마다 총 섭취 칼로리 T를 계산합니다. 여기서 T는 해당 구간의 칼로리 합(calories[i] + calories[i+1] + ... + calories[i+k-1])이며, 다음 조건에 따라 점수가 매겨집니다.
- T가 하한(lower) 미만이면 다이어트를 잘못 수행한 것이므로 1점 감점
- T가 상한(upper) 초과면 다이어트를 잘 수행한 것이므로 1점 가점
- 그 외의 경우에는 정상 범위이므로 점수 변화 없음
처음 점수는 0점에서 시작하며, 최종적으로 다이어터가 획득한 총점을 구하는 것이 목표입니다.
예제 확인
예를 들어 배열이 [6,5,0,0]이고 k = 2, lower = 1, upper = 5라고 가정해 보겠습니다. 이때 출력은 0이 됩니다.
- C[0] + C[1] = 11 > upper(5)이므로 1점 가점
- C[1] + C[2] = 5로 lower와 upper 사이이므로 점수 변화 없음
- C[2] + C[3] = 0 < lower(1)이므로 1점 감점
결국 +1과 -1이 상쇄되어 최종 점수는 0이 됩니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 매번 k개의 요소를 새로 더하면 O(n*k)의 시간이 걸리지만, 윈도우가 이동할 때 앞의 값을 빼고 뒤의 값을 더하는 방식을 사용하면 O(n)으로 최적화됩니다.
알고리즘의 진행 순서는 다음과 같습니다.
- temp := 0으로 초기화한 뒤, 첫 번째 윈도우의 합을 계산합니다.
- right := k-1, left := 0, points := 0으로 설정합니다.
- right가 배열 끝에 도달할 때까지 아래 과정을 반복합니다.
- temp < lower이면 points를 1 감소, temp > upper이면 points를 1 증가
- temp에서 C[left]를 빼고 left와 right를 각각 1씩 증가
- right가 배열 길이 이상이면 반복 종료
- temp에 C[right]를 더해 새로운 윈도우 합을 완성
- 최종 points를 반환합니다.
Python 구현 코드
아래 구현 예제를 통해 동작 방식을 더 잘 이해할 수 있습니다.
class Solution(object):
def dietPlanPerformance(self, c, k, l, u):
temp = 0
for i in range(k):
temp += c[i]
right = k-1
left = 0
points = 0
while right < len(c):
if temp<l:
points-=1
elif temp>u:
points+=1
temp -=c[left]
left+=1
right+=1
if(right >= len(c)):
break
temp+=c[right]
return points
ob1 = Solution()
print(ob1.dietPlanPerformance([6,5,0,0],2,1,5))입력
[6,5,0,0] 2 1 5
출력
0
마무리
이 문제는 고정 크기 윈도우의 합을 유지하면서 조건에 따라 점수를 누적하는 전형적인 슬라이딩 윈도우 연습 문제입니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적이며, 누적합(prefix sum) 기법으로도 동일하게 해결할 수 있습니다.