C++에서 좋은 부분 배열(Nice Subarray)의 개수 세기

정수 배열 nums와 정수 k가 주어졌다고 가정해 보겠습니다. 어떤 부분 배열(subarray) 안에 홀수가 정확히 k개 포함되어 있다면, 그 부분 배열을 "좋은(nice) 부분 배열"이라고 부릅니다. 우리의 목표는 이러한 좋은 부분 배열의 개수를 구하는 것입니다.

예를 들어 배열이 [1,1,2,1,1]이고 k = 3이라면 출력은 2가 됩니다. 조건을 만족하는 부분 배열은 [1,1,2,1]과 [1,2,1,1] 두 가지뿐이기 때문입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

ans := 0, n := nums 배열의 크기로 초기화합니다.
left := 0, right := 0, count := 0으로 설정합니다.
odd라는 배열을 정의하고, nums에 있는 모든 홀수의 인덱스를 순서대로 저장합니다.
odd 배열의 길이가 k보다 크거나 같다면 다음을 수행합니다.
- i는 0부터, j는 k-1부터 시작하여 j가 odd 배열의 마지막 인덱스에 도달할 때까지 i와 j를 각각 1씩 증가시키며 반복합니다.
  - left := odd[i] + 1 (i가 0일 때), 그렇지 않으면 odd[i] - odd[i-1]
  - right := n - odd[j] (j가 odd 배열의 마지막 인덱스일 때), 그렇지 않으면 odd[j+1] - odd[j]
  - ans := ans + left * right
ans를 반환합니다.

핵심 아이디어

홀수의 위치만 모아 놓으면, 연속된 k개의 홀수를 하나의 "윈도우"로 볼 수 있습니다. 각 윈도우에서 왼쪽 경계(left)는 윈도우의 첫 번째 홀수 앞으로 확장할 수 있는 경우의 수를, 오른쪽 경계(right)는 마지막 홀수 뒤로 확장할 수 있는 경우의 수를 나타냅니다. 따라서 각 윈도우마다 left × right개의 좋은 부분 배열이 만들어지며, 이 값을 모두 더하면 정답을 얻을 수 있습니다.

예제 (C++)

다음 구현을 살펴보면 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int ans = 0;
        int n = nums.size();
        int left = 0;
        int right = 0;
        int cnt = 0;
        vector <int> odd;
        for(int i = 0; i < n; i++){
            if(nums[i] % 2 == 1)odd.push_back(i);
        }
        if(odd.size()>=k){
            for(int i = 0, j = k-1; j < odd.size(); i++, j++){
                int left = i==0?odd[i]+1: odd[i] - odd[i-1];
                int right = j==odd.size()-1 ?n-odd[j] : odd[j+1] - odd[j];
                ans += left * right;
            }
        }
        return ans;
    }
};
main(){
    vector<int> v = {1,1,2,1,1};
    Solution ob;
    cout <<ob.numberOfSubarrays(v, 3);
}

입력

[1,1,2,1,1]
3