[LeetCode] 1052. Grumpy Bookstore Owner

https://leetcode.com/problems/grumpy-bookstore-owner/description/

leetcode - Grumpy Bookstore Owner

문제 유형 : 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

There is a bookstore owner that has a store open for n minutes. Every minute, some number of customers enter the store. You are given an integer array customers of length n where customers[i] is the number of the customer that enters the store at the start of the ith minute and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. You are given a binary array grumpy where grumpy[i] is 1 if the bookstore owner is grumpy during the ith minute, and is 0 otherwise.

When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise, they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for minutes consecutive minutes, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

 

n분동안 서점을 여는 사람이 있다.

매 i분에, customers[i]만큼의 손님이 와서 이용하고 i분에나간다.

성격이 나쁜 손님들이 오곤 한다.

grumpy[i]는 이진으로 주어지는데, 1이면 성격이 나쁜 손님들이 온다는 뜻이다.

성격이 나쁘면 만족하지 못한다. 성격이 나쁘지 않으면 만족하고 돌아간다.

서점주인은 minutes분동안 성격을 풀어줄 비밀기술이 있는데, 한 번만 사용가능하다.

최대한 많은 손님들이 만족하는 수를 구하시오.

 

풀이

슬라이딩 윈도우로 해결할 수 있다.

minutes만큼 창 크기를 정해서 처음 그만큼에 대해서, 

grumpy하지않은 손님들은 ans에 누적시키고,

grumpy한 손님들은 maxProfit에 누적시킨다.

 

이제 newProfit을 만들어서 앞으로 매 순간들의 기술을 쓴 구간의 기대점수를 구한다. 그리고 maxProfit과 비교해서 갱신해주면 된다.

이제 i = minutes부터 i < n까지

grumpy하지않은 손님들은 ans에 누적시키고,

grumpy한 손님들은 newProfit에 누적시킨다.

만약 i-minutes의 손님이 grumpy하다면, newProfit에서 빼준다.

newProfit과 maxProfit을 비교해서 maxProfit을 업데이트한다.

 

ans와 maxProfit을 더해 반환한다.

 

코드

C++

class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int ans = 0;
        int n = customers.size();
        int maxProfit = 0;
        for(int i = 0; i < minutes; i++) {
            if(!grumpy[i]) {
                ans += customers[i];
            } else {
                maxProfit += customers[i];
            }
        }
        int newProfit = maxProfit;
        for(int i = minutes; i < n; i++) {
            if(!grumpy[i]) {
                ans += customers[i];
            } else {
                newProfit += customers[i];
            }
            if(grumpy[i - minutes]) {
                newProfit -= customers[i-minutes];
            }
            maxProfit = max(maxProfit, newProfit);
        }

        return ans + maxProfit;
    }
};