LeetCode : 995. Minimum Number of K Consecutive Bit Flips

 

문제)

 

k-비트 뒤집기는 길이가 k인 부분 배열을 선택하여 해당 부분 배열의 모든 0을 1로, 모든 1을 0으로 동시에 변경하는 것을 의미 한다.

이 k-비트 뒤집기를 이용해서 정수 배열 nums에 0이 없도록 하는데 필요한 최소 횟수를 반환하면 된다.

만약 불가능 하다면 -1을 반환하면 되는 문제.

 

난이도 : 상

 

소요시간 및 풀이)

슬라이딩 윈도우로 접근해서 풀면 될 것 같았는데, 아쉽게도 풀지 못했다.

 

소요시간 : 40분

 

정답 코드

    int minKBitFlips(vector<int>& nums, int k)
    {
        int n = nums.size();
        int ans = 0;
        int flip = 0;

        for (int i = 0; i < n; i++)
        {
            if (flip % 2 == nums[i])
            {
                if (i > n - k)
                    return -1;

                ans++;
                flip++;
                nums[i] -= 2;
            }

            if (i >= k - 1 && nums[i - k + 1] < 0)
            {
                flip++;
                nums[i - k + 1] += 2;
            }
        }

        return ans;
    }
};