Skip to content

Instantly share code, notes, and snippets.

@fpdjsns
Created June 15, 2019 03:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fpdjsns/1e7dff3e4b90c1d88e7b60a43acceeaa to your computer and use it in GitHub Desktop.
Save fpdjsns/1e7dff3e4b90c1d88e7b60a43acceeaa to your computer and use it in GitHub Desktop.
[leetcode] 1052. Grumpy Bookstore Owner : https://leetcode.com/problems/grumpy-bookstore-owner/
class Solution {
public:
/*
* 시간복잡도 : O(N)
*/
// sliding window
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int l = 0;
int sum = 0;
int alreadySatisfiedCustomerCnt = 0;
int maxNewSatisfiedCustomerCnt = 0;
for(int r=0; r < customers.size(); r++){
if(l <= r-X){
sum -= customers[l] * grumpy[l];
l++;
}
alreadySatisfiedCustomerCnt += customers[r] * !grumpy[r];
sum += customers[r] * grumpy[r];
maxNewSatisfiedCustomerCnt = max(maxNewSatisfiedCustomerCnt, sum);
}
return alreadySatisfiedCustomerCnt + maxNewSatisfiedCustomerCnt;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment