[LeetCode] 3097. Shortest Subarray With OR at Least K II

https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-ii/description/?envType=daily-question&envId=2024-11-10

leetcode - Shortest Subarray With OR at Least K II

문제 유형: 비트마스킹, 슬라이딩 윈도우

문제 난이도: Medium

 

문제

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray  of nums, or return -1 if no special subarray exists.

 

자연수 배열 nums와 정수 k를 받습니다.

배열의 요소들을 bitwise OR연산했을 때 k보다 크거나 같으면 특별합니다.

특별한 subarray의 최소 길이를 구하시오. 안된다면 -1을 반환하시오.

 

풀이

30짜리 배열 bitArr을 만든다.

bitArr[i] = i번째 비트(LSB로부터)의 누적 개수를 담는다.

 

left와 right를 0부터 시작한다. x에 or값을 누적할것이다.

right를 한 칸씩 밀면서, x에 or연산으로 누적해주고, bitArr에도 비트를 누적시킨다.

  그러고, x가 k보다 크거나 같은 동안, 이제 left를 밀어서 길이를 줄이는것을 시도한다. 이때, 최소길이 업데이트를 해준다.

  nums[left]의 비트들을 bitArr에서 1씩 빼준다. 그러다 그 비트가 0이 되면, x에서도 마스킹해서 없앤다.

  이렇게 유효한동안 left도 밀어준다.

 

만약 한 번이라도 갱신한 적 없다면, -1을 반환하고, 그게 아니라면 최소길이를 반환한다.

 

코드

C++

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> bitArr(30, 0);
        int x = 0;
        int left = 0;
        int ans = INT_MAX;
        for(int right = 0; right < n; ++right) {
            int y = nums[right];
            x  |= y;
            int b = 0;
            while(y > 0) {
                if(y%2 == 1) {
                    bitArr[b]++;
                }
                b++;
                y >>= 1;
            }
            while(left <= right && x >= k) {
                ans = min(ans, right - left + 1);
                y = nums[left];
                int b = 0;
                while(y > 0) {
                    if(y%2 == 1) {
                        bitArr[b]--;
                        if(bitArr[b] <= 0) {
                            x &= ~(1 << b);
                        }
                    }
                    b++;
                    y >>= 1;
                }
                left++;
            }
        }

        return ans == INT_MAX? -1 : ans;
    }
};