[LeetCode] 995. Minimum Number of K Consecutive Bit Flips

https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/description/

leetcode - Minimum Number of K Consecutive Bit Flips

문제 유형 : 그리디 / 비트마스킹 / 슬라이딩 윈도우

문제 난이도 : Hard

 

문제

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

A subarray is a contiguous part of an array.

 

이진 배열 nums와 정수 k를 받는다.

k비트 반전은 k길이의 서브어레이를 골라서 1 -> 0, 0 -> 1로 하는 움직임이다.

모든 배열의 요소를 1로 만들기 위해 k비트 반전을 해야하는 횟수를 구하시오.

불가능하면 -1을 반환하시오.

 

풀이

그리디한 접근으로 풀 수 있다. 

처음부터 순차적으로 k비트반전을 시키면서 나아가면 된다.

k비트의 서브어레이를 반전시키므로, 중간에 1도 0으로 바뀌기에, 그 부분들도 다시 뒤집어줘야 한다.

isFlipped배열을 만들어서, 배열에 플립되었는지에 대한 여부를 저장한다.

 

배열의 각 요소를 순회하면서, 만약 nums[i]와, k이전의 인덱스의 뒤집었는지 홀/짝 (i-k번째를 뒤집으면 이것도 반전되므로)

을 xor해주면, 이전 플립을 반영한 값이 나온다.

이 값이 0이라면, 뒤집어야 한다.

isFlipped에 1을 저장하고, flip반전을 시켜준다.

 

코드

C++

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

        for(int i = 0; i < n; i++) {
            if(i >= k) {
                flip ^= isFlipped[i - k];
            }

            if((nums[i] ^ flip) == 0) {
                if(i + k > n) return -1;
                flip ^= 1;
                isFlipped[i] = 1;
                ans++;
            }
        }
        
        return ans;
    }
};