Grumpy Bookstore Owner

Sliding window 문제를 풀었다. 솔직히 쉬운 문제인데 생각보다 너무 헤맸다. 이유는... 문제를 잘 못 읽었다.

Sliding Window 패턴은 내가 많이 풀어봤을 떄 아래와 같다.

1. 요구하는 조건 체크 (이 경우, grumpy 가 1일 때 뭐를 해줘라)

2. 그 조건을 벗어난 경우, 범위 조정 (이 경우, minutes 와 같아질 경우 max_minute 업데이트 및 start 를 옮김으로서 범위 조정)

3. 카운트 (변동 가능성 있음) -> 이때는 start 포인터를 옮겨 주면서 tmpMax 카운트를 변동해야했음

조건 체크, 범위 조정, 카운트 (변경 가능) 이 3개만 기억해도 웬만한 슬라이딩은 다 풀 수 있을거같다. FOR 루프를 이용한 슬라이딩 방법도 있었지만 난 While 룹을 활용한 슬라이딩 방법이 더 좋은거같다.

class Solution {
    /*
    Time Complexity : O(N) 
    Space Compleixty : O(1) 
    */
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int max_minute = 0; 
        for(int i = 0; i < customers.size(); i++){
            int grump = grumpy[i]; 
            if(grump == 0) max_minute += customers[i]; 
        }

        int start = 0, end = 0; 
        int tmpMax = max_minute; 
        while(end < grumpy.size()){

            if(grumpy[end] == 1){
                tmpMax += customers[end]; 
                //cout << start << ' ' << end << ' ' << tmpMax << endl; 
            }

            while(end - start + 1 >= minutes){
                //cout << start << ' ' << end << ' ' << tmpMax << endl; 
                max_minute = max(max_minute, tmpMax); 
                if(grumpy[start] == 1){
                    tmpMax -= customers[start];
                }
                start++; 
            }
            end++; 
        }

        return max_minute; 
    }
};