[LeetCode] 1248. Count Number of Nice Subarrays

https://leetcode.com/problems/count-number-of-nice-subarrays/description/

leetcode - Count Number of Nice Subarrays

문제 유형 : 슬라이딩 윈도우, 투포인터

문제 난이도 : Medium

 

문제

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

 

정수배열 nums와 정수 k가 주어집니다. 연속적인 부분배열의 요소에 홀수의 요소가 정확히 k개 있으면, nice한 subarray입니다.

nice한 subarray의 개수를 구하시오.

 

풀이

투 포인터와 슬라이딩 윈도우로 해결가능하다.

우선, k개의 홀수를 가지도록 계속해서 right를 증가시키며 읽어들인다.

그리고, k개가 되면 짝수인동안 계속 right를 증가시키면서, k번째 홀수 이후의 짝수의 개수를 구한다.

제일 왼쪽의 홀수를 찾기 위해서, left를 증가시키면서 짝수의 개수를 누적시킨다.

nice한 subarray의 개수는, 매번 left이후로 k개의 홀수를 담고 최대한 right를 오른쪽으로 진행시켰다고 가정할 때,

(가장 왼쪽 홀수의 이전의 짝수의 개수 + 1) * (가장 오른쪽 홀수 이후의 짝수의 개수 * 1)의 누적들이다.

이 연산을 해주고, 다음에는 홀수가 하나 있다는 뜻 혹은 배열의 끝이라는 뜻이니, odds에서 1을 제거하고, left++을 해서 양끝을 새로 업데이트한다.

 

코드

C++

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, right = 0;
        int odds = 0;
        int ans = 0;
        while(right < n) {
            // 홀수 k개되도록 채워..
            while(right < n && odds < k) {
                if(nums[right]%2) {
                    odds++;
                }
                right++;
            }
            // 짝수인동안 계속 진행...
            int y = 1;
            while(right < n && nums[right] %2 == 0) {
                right++;
                y++;
            }
            
            int x = 1;
            while(left <= right && nums[left] %2 == 0) {
                x++;
                left++;
            }
            if(odds == k) ans += 1 * y * x;
            left++;
            odds--;
        }
        return ans;
    }
};