[Algorithm][LeetCode 2962] Count Subarrays Where Max Element Appears at Least K Times

최대값이 k번 이상 등장하는 서브어레이 개수

문제 설명

정수 배열 nums와 양의 정수 k가 주어집니다.

조건: 배열 내의 최대값이 적어도 k번 이상 등장하는 모든 서브어레이의 개수를 구하시오.

예시 1:

Input: nums = [1,3,2,3,3], k = 2
Output: 6
Explanation: 
다음과 같은 서브어레이가 조건을 만족함:
[1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3], [3,3]

예시 2:

Input: nums = [1,4,2,1], k = 3
Output: 0
Explanation: 
어떤 서브어레이도 최대값인 4를 3번 이상 포함하지 않음.

제약 조건:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁶
• 1 <= k <= 10⁵

---

풀이 전략

처음에는 map을 활용해서 해결하려고 했습니다. 하지만 k 이상이라는 조건은 단일 조건이 아닌 누적 조건이기 때문에, 해시맵보다는 슬라이딩 윈도우(sliding window) 방식이 더 적합하다고 판단했습니다.

슬라이딩 윈도우 방식:

1. 배열을 순회하며 각 요소가 최대값인지 확인
2. 최대값이면 frequency를 증가
3. frequency가 k 이상이 되는 순간, left 포인터를 증가시키며 조건을 만족하지 않을 때까지 줄여나감
4. 그때의 left 값을 결과에 더함

코드 구현:

const countSubarrays = (nums, k) => {
    const max = Math.max(...nums); // 최대값
    let frequency = 0; // 최대값이 등장한 횟수
    let count = 0; // 결과 값 (조건을 만족하는 서브어레이 개수)
    let left = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === max) frequency++;

        // 최대값 등장 횟수가 k 이상일 경우
        while (frequency >= k) {
            if (nums[left] === max) frequency--;
            left++;
        }

        count += left; // 조건을 만족하는 서브어레이 개수 누적
    }

    return count;
};

---

시간복잡도: O(n)
공간복잡도: O(1)