문제 링크

• 좀 더 간단한 아이디어..!
  • 나: 지울 수 있는지 지워보고 안 되면 원복
  • 풀이2: 현재 가능하면 범위 삭제(가장 앞에 추가된 애 삭제).
    • 어차피 이 길이는 뒤에 원소가 추가되도 답이 될 수 없다. (지우고 나서 k보다 작아도 원복할 필요 없다.)
• subarray는 연속인 배열을 말한다.

아래는 GPT의 답변

네, 일반적으로 subarray는 “연속된” 배열을 의미합니다.
예를 들어, 배열 [1, 2, 3, 4]의 subarray는 [1, 2], [2, 3, 4], [3] 등처럼 원래 배열의 일부 연속된 요소들을 포함하는 부분 배열들입니다. 이와 달리 subset은 배열 요소가 반드시 연속될 필요가 없으며, [1, 3], [2, 4]처럼 요소들이 비연속적으로 포함될 수 있습니다.
C++에서 알고리즘 문제를 풀 때 subarray와 subset을 혼동하지 않도록 주의해야 합니다. 문제에서 subarray를 요구한다면 연속된 부분 배열만을 고려해야 합니다.

내 코드

• 117ms, 88.21MB

class Solution {
public:
	int minimumSubarrayLength(vector<int>& nums, int k) {
		// subarray: 연속인 배열
		int s{}, e{};
		int answer = 1 << 30;

		vector<int> bits(32, 0);
		for (int s{}, e{}; s < static_cast<int>(nums.size()); ++s) { // [e, s]
			// 추가
			int tmp = nums[s];
			int place{};
			while (tmp) {
				if (tmp & 1) bits[place]++;
				tmp >>= 1; ++place;
			}

			int now{};
			for (int i{}; i < 32; ++i) {
				if (bits[i]) now |= (1 << i);
			}
			if (now >= k) answer = min(answer, s - e + 1);

			// 제거
			while (e < s) {
				tmp = nums[e];
				place = 0;
				while (tmp) {
					if (tmp & 1) bits[place]--;
					tmp >>= 1; ++place;
				}

				now = 0;
				for (int i{}; i < 32; ++i) {
					if (bits[i]) now |= (1 << i);
				}

				if (now < k) { // 못 지움 원복하고 break
					tmp = nums[e];
					place = 0;
					while (tmp) {
						if (tmp & 1) bits[place]++;
						tmp >>= 1; ++place;
					}
					break;
				}
				++e;
				answer = min(answer, s - e + 1);
			}
		}
		if (answer == 1 << 30) answer = -1;
		return answer;
	}
};

Solution

Approach 1: Binary Search

• 842ms, 88.69MB
• Complexity
  • Let n be the length of the nums array.
  • Time Complexity: $O(n \cdot \log n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int left = 1;
        int right = nums.size();
        int minLength = -1;

        // Binary search on the length of subarray
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (hasValidSubarray(nums, k, mid)) {
                minLength = mid;
                right = mid - 1;  // Try to find smaller length
            } else {
                left = mid + 1;  // Try larger length
            }
        }

        return minLength;
    }

private:
    // Checks if there exists a subarray of given length whose bitwise OR is >=
    // k
    bool hasValidSubarray(vector<int>& nums, int targetSum, int windowSize) {
        int arrayLength = nums.size();
        vector<int> bitCounts(32,
                              0);  // Tracks count of set bits at each position

        // Sliding window approach
        for (int right = 0; right < arrayLength; right++) {
            // Add current number to window
            updateBitCounts(bitCounts, nums[right], 1);

            // Remove leftmost number if window exceeds size
            if (right >= windowSize) {
                updateBitCounts(bitCounts, nums[right - windowSize], -1);
            }

            // Check if current window is valid
            if (right >= windowSize - 1 &&
                convertBitCountsToNumber(bitCounts) >= targetSum) {
                return true;
            }
        }
        return false;
    }

    // Updates bit count array when adding/removing a number from window
    void updateBitCounts(vector<int>& bitCounts, int number, int delta) {
        for (int bitPosition = 0; bitPosition < 32; bitPosition++) {
            // Check if bit is set at current position
            if (((number >> bitPosition) & 1) != 0) {
                bitCounts[bitPosition] += delta;
            }
        }
    }

    // Converts bit count array back to number using OR operation
    int convertBitCountsToNumber(vector<int>& bitCounts) {
        int number = 0;
        for (int bitPosition = 0; bitPosition < 32; bitPosition++) {
            if (bitCounts[bitPosition] != 0) {
                number |= 1 << bitPosition;
            }
        }
        return number;
    }
};

Approach 2: Sliding Window

• 63ms, 88.32MB
• Complexity
  • Let n be the length of the nums array.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int minLength = INT_MAX;
        int windowStart = 0;
        int windowEnd = 0;
        vector<int> bitCounts(32,
                              0);  // Tracks count of set bits at each position

        // Expand window until end of array
        while (windowEnd < nums.size()) {
            // Add current number to window
            updateBitCounts(bitCounts, nums[windowEnd], 1);

            // Contract window while OR value is valid
            while (windowStart <= windowEnd &&
                   convertBitCountsToNumber(bitCounts) >= k) {
                // Update minimum length found so far
                minLength = min(minLength, windowEnd - windowStart + 1);

                // Remove leftmost number and shrink window
                updateBitCounts(bitCounts, nums[windowStart], -1);
                windowStart++;
            }

            windowEnd++;
        }

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

private:
    // Updates bit count array when adding/removing a number from window
    void updateBitCounts(vector<int>& bitCounts, int number, int delta) {
        for (int bitPosition = 0; bitPosition < 32; bitPosition++) {
            // Check if bit is set at current position
            if ((number >> bitPosition) & 1) {
                bitCounts[bitPosition] += delta;
            }
        }
    }

    // Converts bit count array back to number using OR operation
    int convertBitCountsToNumber(const vector<int>& bitCounts) {
        int result = 0;
        for (int bitPosition = 0; bitPosition < 32; bitPosition++) {
            if (bitCounts[bitPosition] != 0) {
                result |= 1 << bitPosition;
            }
        }
        return result;
    }
};