문제 개요
길이가 같은 두 개의 리스트 customers(방문 고객 수)와 mood(기분 상태), 그리고 정수 k가 주어집니다. 매 분 i에 customers[i]명의 고객이 매장을 방문하며, mood[i]가 1이면 해당 고객들은 행복하고, 0이면 불행한 상태를 의미합니다.
여기서 우리는 길이가 k인 연속된 구간의 mood 값을 모두 1로 변경할 수 있습니다(예: 프로모션 진행). 이 조건에서 행복하게 만들 수 있는 고객 수의 최댓값을 구하는 것이 목표입니다.
입력 예시
다음과 같은 입력이 주어졌다고 가정해 보겠습니다.
- customers = [2, 3, 6, 6, 3]
- mood = [1, 1, 0, 0, 0]
- k = 2
이 경우 출력은 17이 됩니다. mood[2]와 mood[3]을 1로 설정하면 원래 행복했던 고객(2 + 3 = 5)과 새롭게 행복해진 고객(6 + 6 = 12)을 합쳐 총 17명의 고객이 행복하게 됩니다.
풀이 방법: 슬라이딩 윈도우 활용
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 이미 행복한 고객(mood가 1)의 합계 s를 먼저 계산합니다.
- 불행한 고객(mood가 0)만 누적 배열 a에 기록하여, 길이 k인 어떤 연속 구간이 가장 많은 불행한 고객을 포함하는지 찾습니다.
- s에 해당 구간의 불행한 고객 수 최댓값 d를 더하면 정답이 됩니다.
알고리즘 단계
- n := mood의 길이
- a := 크기가 (n + 1)인 리스트, 0으로 초기화 (누적합 저장용)
- s := 0 (원래 행복한 고객의 합)
- i를 0부터 n-1까지 반복:
- a[i+1] := a[i]
- mood[i]가 1이면: s := s + customers[i]
- 그렇지 않으면: a[i+1] := a[i+1] + customers[i]
- d := 0
- i를 k부터 n까지 반복하며: d := max(d, a[i] - a[i-k])
- s + d 반환
Python 코드 예제
def solve(customers, mood, k):
n = len(mood)
a = [0] * (n + 1)
s = 0
for i in range(n):
a[i + 1] = a[i]
if mood[i]:
s += customers[i]
else:
a[i + 1] += customers[i]
d = 0
for i in range(k, n + 1):
d = max(d, a[i] - a[i - k])
return s + d
customers = [2, 3, 6, 6, 3]
mood = [1, 1, 0, 0, 0]
k = 2
print(solve(customers, mood, k))실행 결과
입력:
[2, 3, 6, 6, 3], [1, 1, 0, 0, 0], 2
출력:
17
마무리 정리
이 알고리즘은 시간 복잡도 O(n)으로 동작합니다. 누적합 배열을 사용하면 각 윈도우 구간의 합을 빠르게 계산할 수 있어, 가능한 모든 k 크기의 구간을 효율적으로 탐색할 수 있습니다. 슬라이딩 윈도우와 누적합(prefix sum)을 결합하면 이처럼 구간 기반 최적화 문제를 간결하게 해결할 수 있다는 점을 기억해 두면 유용합니다.