[LeetCode] 1004번: Max Consecutive Ones 3

문제 링크: https://leetcode.com/problems/max-consecutive-ones-iii/

Max Consecutive Ones III - LeetCode

 

학교 실습에서도 슬라이딩 윈도우 문제가 등장했기 때문에 더 중요성을 체감하는 중이다.

 

이 문제는 학교 실습 문제보다는 훨씬 간단한 슬라이딩 윈도우 문제였다.

 

두 포인터 start와 end는 모두 인덱스 0을 가리키는 상태에서 시작한다.

만약 end포인터가 가리키는 배열의 값이 1인 경우에는 아무런 문제 없이 subarray 길이를 늘릴 수 있다.

또한 만약 end포인터가 가리키는 배열의 값이 0이지만 0을 1로 바꾼 횟수가 K보다 적은 경우에는 0을 1로 바꾼 후 subarray 길이를 늘릴 수 있다.

하지만 만약 end 포인터가 가리키는 배열의 값이 0인데 0을 1로 바꾼 횟수도 K번이어서 더 이상 subarray 길이를 늘릴 수 없을 때는 start 포인터를 1 증가시킴으로써 윈도우(subarray) 길이를 줄여줘야 한다.

이때 start가 가리키던 배열 값이 0이었다면 0을 1로 바꾼 횟수를 감소시켜줘야 함을 잊지 말자.

 

class Solution {
public:
	int longestOnes(vector<int>& A, int K) {
		int s = 0, e = 0, ans = 0, zeroCnt = 0;
		while (e < A.size()) {
			if (A[e] == 1) {
				if (ans < e - s + 1)
					ans = e - s + 1;
				e++;
			}

			else if (zeroCnt < K && A[e] == 0) {
				zeroCnt++;
				if (ans < e - s + 1)
					ans = e - s + 1;
				e++;
			}

			else if (zeroCnt == K) {
				if (A[s] == 0) {
					zeroCnt--;
				}
				s++;
				if (ans < e - s + 1)
					ans = e - s + 1;
			}
		}
		return ans;
	}
};