[2024] day 174. Leetcode 1052. Grumpy Bookstore Owner

gunny·2024년 6월 21일

leetcode 1052. Grumpy Bookstore Owner leetcode 1052. Grumpy Bookstore Owner python

코딩테스트

목록 보기

488/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 21일 (금)
Leetcode daily problem

1052. Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/?envType=daily-question&envId=2024-06-21

Problem

n분 동안 문을 여는 서점 주인이 있고, 매분마다 일부 고객이 서점에 들어온다. 길이 n의 정수 배열 customers이 제공되고, 여기서 customers[i]은 i번째 분의 시작 시점에 서점에 들어오는 고객의 수를 나타내고, 이 고객은 해당 분이 끝나면 서점을 떠난다.

어느 시점인 분에는 서점 주인이 기분이 나빠지는데 grumpy라는 이분 배열이 주어지고 grumpy[i] 는 i번째 분 동안 서점 주인이 기분이 나쁘다면 1, 나쁘지 않으면 0이다.
이때 서점 기분이 나쁘면(1) 해당 분의 고객은 만족하지 못하고, 나쁘지 않으면(0)이면 해당 분의 고객은 만족하게 된다.

서점 주인은 연속된 분 동안 자신의 기분을 좋게 유지하는 비법을 알고 있지만, 한 번만 사용할 수 있다.

하루에 만족할 수 있는 최대 고객 수를 반환한다.

Solution

Sliding Window

이 문제는 서점 주인이 특정 시간 동안 우호적이지 않는 grumpy 시간이지만 주인이 친절하게 행동할 수 있는 시간을 찾아 최대한 많은 손님을 만족시켜야 하는 것이다. 이를 위해서 sliding window 알고리즘을 사용한다.

'x'분 동안 최대한 많은 손님을 만족시킬 수 있는 구간을 모두 검사하는 것은 비효율적이므로, 고정 크기('x') 의 윈도우를 배열 위에서 이동 시키면서 최적의 구간을 효율적으로 찾는다.

처음 'x'분 동안 비우호적인 시간에 방문한 손님의 수를 계산해서 저장하고,
초기의 최대 만족하지 않은 손님의 수를 설정한다.

그리고 'x'부터 주어진 customers (손님의 수) 까지 반보갛면서, 현재 시간이 비우호적이면 만족하지 않는 손님의 수를 추가한다.
이전 윈도우 시작 시간이 비우호적이었다면 해당 수 만큼 만족하지 않았던 손님의 수를 빼면서 해당 값을 업데이트 해가면서 최대로 만족하지 않는 손님의 수를 유지한다.

그리고 주인이 친절했던 시간의 손님의 수를 모두 더하고
계속 업데이트했던 만족하지 않는 손님의 수를 더해서 최종적으로 만족한 손님의 수를 계산한다.

Code

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        unsatisfied_customers = 0
        
        for i in range(minutes):
            unsatisfied_customers += customers[i] * grumpy[i]
            
        max_unsatisfied_customers = unsatisfied_customers
        
        for i in range(minutes, n):
            unsatisfied_customers += customers[i] * grumpy[i]
            unsatisfied_customers -= customers[i-minutes] * grumpy[i-minutes]
            
            max_unsatisfied_customers = max(max_unsatisfied_customers, unsatisfied_customers)
            
        
        ans = max_unsatisfied_customers
        
        for i in range(n):
            ans += customers[i] * (1-grumpy[i])
            
        return ans