문제

• 링크: https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/?envType=daily-question&envId=2025-04-29

요즘 슬라이딩 윈도우로만 풀다보니 다른 방법으로 풀기 귀찮아졌다

코드

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        count = 0
        maxCount = 0
        n = len(nums)
        maxN = max(nums)

        l = 0
        r = 0

        for r in range(n):
            if nums[r] == maxN:
                maxCount += 1
            while maxCount >= k:
                count += n - r
                if nums[l] == maxN:
                    maxCount -= 1
                l += 1
        return count

설명

• 조건(인풋 배열의 max값이 k번 이상 들어가있는 서브어레이인가)을 만족하는 서브배열의 갯수를 찾는 문제

• 슬라이딩 윈도우 기법으로 풀면 쉽게 풀 수 있다.

• l과 r 모두 index 0 에서 시작

• r이 배열의 최대값 원소와 같다면 maxCount를 1 더해줌

• 누적 maxCount가 k 값보다 많다면

  • 총 서브트리 개수인 count를 l부터 r까지로 만들수 있는 서브트리중 조건을 만족하는 트리 수만큼 더해줌(n-r개)
  • 그 후 현재 l이 max값과 같다면 l을 늘렸을 때 max인 값이 하나 줄어드는 것이니 maxCount 를 -1 해준 뒤에 l 값을 +1 해 줌

• 모든 반복문 종료 후 count return으로 종료

다른 방버브로도 풀 수 있을것 같다.