문제 소개
한 명의 서점 주인이 customers 리스트 길이만큼의 시간(분) 동안 가게를 운영한다고 가정해 보겠습니다. 매 분마다 일정 수의 고객(customers[i])이 가게에 들어오고, 해당 분이 끝나면 그 고객들은 모두 떠납니다. 이때 어떤 분에는 주인이 기분이 나쁜 상태일 수 있습니다.
주인이 i번째 분에 기분이 나쁘다면 grumpy[i] = 1이고, 그렇지 않다면 grumpy[i] = 0입니다. 주인이 기분이 나쁜 분에 방문한 고객들은 불행해지며, 반대로 주인이 평온한 분에 방문한 고객들은 행복해집니다.
서점 주인은 자신이 연속 X분 동안 기분 나쁜 상태가 되지 않도록 만들어 주는 특별한 기술을 알고 있는데, 이 기술은 하루에 딱 한 번만 사용할 수 있습니다. 우리의 목표는 하루 전체에서 행복할 수 있는 고객 수의 최댓값을 구하는 것입니다.
예시
입력이 다음과 같다고 합시다.
customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1], X = 3
이 경우 출력은 16입니다. 주인이 마지막 세 분 동안 기분 나쁜 상태가 되지 않기 때문입니다. 따라서 행복할 수 있는 최대 고객 수는 다음과 같습니다.
1 + 1 + 1 + 1 + 7 + 5 = 16
해결 접근 방법
이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- i := 0, j := 0으로 초기화하고, sums는 빈 리스트, temp는 0으로 설정합니다.
- while j − i + 1 < X 조건 동안 반복합니다.
- grumpy[j]가 1이면 temp := temp + customers[j]
- j를 1 증가시킵니다.
- 리스트 [temp, i, j]를 sums 배열에 삽입합니다.
- i와 j를 각각 1씩 증가시킵니다.
- while j < 고객 리스트의 길이 조건 동안 반복합니다.
- grumpy[i − 1]이 1이면 temp := temp − customers[i − 1]
- grumpy[j]가 1이면 temp := temp + customers[j]
- [temp, i, j]를 sums 배열에 삽입합니다.
- i와 j를 각각 1씩 증가시킵니다.
- sums 배열을 내부 리스트의 첫 번째 요소(temp 값)를 기준으로 정렬합니다.
- index1 := sums 마지막 리스트의 두 번째 요소, index2 := sums 마지막 리스트의 세 번째 요소로 설정합니다.
- index1부터 index2까지의 범위에서 grumpy[i] := 0으로 변경합니다.
- ans := 0으로 설정합니다.
- 0부터 고객 리스트 길이까지 반복합니다.
- grumpy[i]가 0이면 ans := ans + customers[i]
- ans를 반환합니다.
핵심 아이디어는 크기가 X인 윈도우를 이동시키면서, 각 위치에서 '기술을 사용해 얻을 수 있는 추가 고객 수'를 계산하는 것입니다. 윈도우 내에서 grumpy가 1인 분들의 고객 수를 합산하면, 기술 사용으로 행복해질 수 있는 고객 수를 알 수 있고, 그중 최댓값을 선택하면 됩니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution(object):
def maxSatisfied(self, customers, grumpy, X):
i = 0
j = 0
sums = []
temp = 0
while j-i+1<X:
if grumpy[j]:
temp+=customers[j]
j+=1
sums.append([temp,i,j])
i+=1
j+=1
while j<len(customers):
if grumpy[i-1]:
temp-=customers[i-1]
if grumpy[j]:
temp+=customers[j]
sums.append([temp,i,j])
i+=1
j+=1
sums =sorted(sums,key = lambda v : v[0])
index1 = sums[-1][1]
index2 = sums[-1][2]
for i in range(index1,index2+1):
grumpy[i] = 0
ans = 0
for i in range(len(customers)):
if not grumpy[i]:
ans+=customers[i]
return ans
ob = Solution()
print(ob.maxSatisfied([1,0,1,2,1,1,7,5],[0,1,0,1,0,1,0,1],3))입력
[1,0,1,2,1,1,7,5] [0,1,0,1,0,1,0,1] 3
출력
16
마무리
이 문제는 LeetCode의 대표적인 슬라이딩 윈도우 유형 중 하나로, 고정된 크기의 윈도우 안에서 손실되는 값을 관리하는 방식이 핵심입니다. 위와 같이 구현하면 시간 복잡도 O(n), 공간 복잡도 O(n)으로 문제를 해결할 수 있습니다.