1. 문제 소개

3318. Find X-Sum of All K-Long Subarrays I

2. 나의 풀이법

문제의 설명대로 길이 k의 부분수열에서 빈도수를 계산하고 자주 등장한 숫자들로 x_sum을 답에 넣었다.

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        ans = []
        for i in range(n-k+1):
            cnt = Counter(nums[i:i+k])
            freq = sorted(cnt.items(), key=lambda x: (x[1], x[0]), reverse=True)
            x_sum = sum(v * f for v, f in freq[:x])
            ans.append(x_sum)
        return ans

3. 다른 풀이법

슬라이딩 윈도우를 사용한 다른 풀이법도 존재한다.

from collections import defaultdict
from typing import List

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        freq = defaultdict(int)

        for i in range(k):
            freq[nums[i]] += 1

        def compute_x_sum(freq, x):
            items = [(v, f) for v, f in freq.items()]
            items.sort(key=lambda t: (-t[1], -t[0]))
            total = 0
            for i in range(min(x, len(items))):
                v, f = items[i]
                total += v * f
            return total

        ans = [compute_x_sum(freq, x)]

        for i in range(k, n):
            add = nums[i]
            rem = nums[i - k]
            freq[add] += 1
            freq[rem] -= 1
            if freq[rem] == 0:
                del freq[rem]
            ans.append(compute_x_sum(freq, x))

        return ans

4. 결론

다양한 접근법이 존재하는 문제였다.