리스트 nums와 두 개의 값 k, target이 주어졌을 때, 크기가 정확히 k이면서 평균값이 target 이상인 연속된 부분 리스트(sublist)의 개수를 구하는 문제입니다.
예를 들어 입력이 nums = [1, 10, 5, 6, 7], k = 3, target = 6이라면 출력은 2가 됩니다. 길이 3인 부분 리스트 중 [10, 5, 6]의 평균은 7, [5, 6, 7]의 평균은 6으로, 이 두 개가 조건을 만족하기 때문입니다.
접근 방법: 슬라이딩 윈도우(Sliding Window)
모든 부분 리스트를 매번 처음부터 다시 계산하면 비효율적입니다. 대신 슬라이딩 윈도우 기법을 사용하면 리스트를 한 번만 순회하면서 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 평균 비교를 합 비교로 변환: target에 미리 k를 곱해두면, "부분 리스트의 평균이 target 이상"이라는 조건을 "부분 리스트의 합이 target × k 이상"이라는 조건으로 바꿀 수 있습니다. 이렇게 하면 나눗셈 없이 정수 연산만으로 판단할 수 있어 정확하고 빠릅니다.
- 윈도우 유지: 윈도우가 오른쪽으로 한 칸 이동할 때마다 새로 들어온 요소는 더하고, 윈도우에서 벗어난 요소는 빼서 현재 합을 상수 시간에 갱신합니다.
- 조건 검사: 윈도우 크기가 k에 도달한 시점(i ≥ k-1)부터 합을 target × k와 비교하여 조건을 만족하면 카운트를 증가시킵니다.
알고리즘 단계
- target := target × k
- sum := 0, ans := 0
- 리스트의 각 인덱스 i와 값 n에 대해:
- i ≥ k이면, sum에서 nums[i − k]를 뺀다 (윈도우에서 벗어난 요소 제거)
- sum에 n을 더한다 (새 요소 추가)
- i ≥ k − 1이면(윈도우가 가득 찼으면), sum ≥ target일 때 ans를 1 증가시킨다
- ans를 반환한다
예제 코드
class Solution:
def solve(self, nums, k, target):
target *= k
total = 0
ans = 0
for i, n in enumerate(nums):
if i >= k:
total -= nums[i - k]
total += n
if i >= (k - 1):
if total >= target:
ans += 1
return ans
ob = Solution()
nums = [1, 10, 5, 6, 7]
k = 3
target = 6
print(ob.solve(nums, k, target))
입력
[1, 10, 5, 6, 7], 3, 6
출력
2
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번만 순회하며 각 단계의 연산은 상수 시간입니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 몇 개의 변수만 사용합니다.
참고: 파이썬에서는 내장 함수 sum()과 이름이 겹치지 않도록 변수명을 total처럼 지정하는 것이 좋습니다. 원본 코드에서 sum을 변수로 사용하면 해당 스코프 안에서 내장 함수를 덮어쓰게 되어 이후 코드에서 오류를 일으킬 수 있습니다.