[Sliding Window][Medium] 1004. Max Consecutive Ones III

https://leetcode.com/problems/max-consecutive-ones-iii/description

Max Consecutive Ones III - LeetCode

 

Q. 0과 1로 구성된 주어진 배열 nums와 정수 k가 있을때, 최대의 1로 이루어진 연속된 sub array길이를 찾아라. 이때 0을 k만큼 1로 바꿀 수 있다고 가정한다. 

 

Solution. 

 '연속된' 1의 수를 구하는 문제이므로, 약간 복잡하게 느껴 질 수 있다. 

 하지만 k만큼 0을 카운트하고, 그 길이의 최대값을 구하면 답을 구할 수 있다.

 잠시 생각해야 할 부분은 k수만큼 0변환을 다 소진하면, 다시 카운팅을 시작해야 할 부분이다. 즉, 변환수를 다 소진했는데 다시 0 이 나온다면 이 지점을 포함해서 0의 k소진이 다 끝나게 되는 첫 지점부터 다시 카운팅을 시작한다. 

 -> 즉, 추가적으로 나온 0만큼 sub array 앞에서 0을 하나 제외시켜 주면, 제외된 바로 다음 index 부터 새 카운팅할 배열의 시작 지점이 된다.  

 

int longestOnes(vector<int>& nums, int k)
{
    int left = 0;
    int flip = k;
    int ret = 0;
    for (int right = 0; right < nums.size(); ++right)
    {
        int cur = nums[right];
        if (cur == 0)
            --flip;

		// k의 소진 지점까지 left 전진.
        while(flip < 0)
        {
            cur = nums[left++];
            if (cur == 0)
                ++flip;
        }

		// 모든 k를 소진하지 않고, 배열이 종료될 상황을 고려 flip>=0.
        if (flip >= 0)				
            ret = max(ret, right - left + 1);
    }
    return ret;
}