[Leetcode 1052번 문제] 1052. Grumpy Bookstore Owner

문제 상황

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분 동안 상점을 연다, 1분마다 customers[i] 명의 사람이 가게로 들어온다. 그리곤 다음 1분 안에 떠난다.

최대 연속된 minutes동안 심술이 안나게됨 단 1번만 쓸 수 있음

상점이 I분에 심술나있으면 고객에 나가고 아니면 고객이 기분이 안좋음

최대의 고객이 만족하는 방법을 찾으라.

연속된 가격이니

입력

• n == customers.length == grumpy.length
• 1 <= minutes <= n <= 2 * 10 ^ 4
• 0 <= customers[i] <= 1000
• grumpy[i] is either 0 or 1.

출력

최대의 고객이 만족했을 때의 그 고객의 숫자 정수

과정

grumpy와 minues 는 길다 문제를 O(n ^ 2)로 풀기 어렵게 해놨지만. 모든지점에서 필요한 값이 단순히 왼쪽(또는 오른쪽) minutes - 1개 중 조건에 맞는 수이다. 따라서 

1차원 슬라이딩 윈도우로 얼마든지 풀 수 있을 것 같다.

알고리즘 개요도

알고리즘

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