파이썬(Python)으로 크기 K의 각 윈도우에서 고유한 숫자 개수 목록 구하기

문제 개요

숫자 리스트 nums와 정수 k가 주어졌을 때, 크기가 k인 각 윈도우(연속된 부분 구간)에 포함된 서로 다른 숫자의 개수를 순서대로 담은 리스트를 구하는 프로그램을 작성해 보겠습니다.

예를 들어 입력이 nums = [2, 2, 3, 3, 4], k = 2라고 가정하면, 윈도우는 차례대로 [2, 2], [2, 3], [3, 3], [3, 4]이고 각 윈도우의 고유한 숫자 개수는 1, 2, 1, 2이므로 최종 출력은 [1, 2, 1, 2]가 됩니다.

풀이 접근 방법: 슬라이딩 윈도우 기법

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 해시 맵(딕셔너리)을 함께 사용하면 효율적으로 해결할 수 있습니다. 매번 윈도우 전체를 새로 세는 대신, 윈도우가 한 칸씩 이동할 때 새로 들어오는 요소와 빠져나가는 요소만 갱신하는 방식입니다.

먼저 첫 번째 윈도우(nums[0]부터 nums[k-1])에 포함된 요소들의 빈도수를 저장하는 딕셔너리 c를 생성합니다.
결과를 저장할 빈 리스트 ans를 준비합니다.
인덱스 k부터 리스트 끝까지 다음 과정을 반복합니다.
- 현재 딕셔너리 c의 크기(서로 다른 요소의 개수)를 ans의 끝에 추가합니다.
- 새로 윈도우에 들어오는 요소 nums[i]의 빈도를 1 증가시킵니다.
- 윈도우에서 벗어나는 요소 nums[i-k]의 빈도를 1 감소시킵니다.
- 감소 후 빈도가 0이 되면, 해당 값은 더 이상 윈도우에 존재하지 않으므로 딕셔너리에서 키를 삭제합니다.
반복이 끝난 뒤 마지막 윈도우의 고유 요소 개수를 ans에 추가하고 반환합니다.

구현 예제

from collections import Counter

class Solution:
    def solve(self, nums, k):
        c = Counter()
        for i in range(k):
            c[nums[i]] += 1
        ans = []
        for i in range(k, len(nums)):
            ans.append(len(c))
            c[nums[i]] += 1
            c[nums[i - k]] -= 1
            if c[nums[i - k]] == 0:
                del c[nums[i - k]]
        ans.append(len(c))
        return ans

ob = Solution()
nums = [2, 2, 3, 3, 4]
print(ob.solve(nums, 2))

입력

[2, 2, 3, 3, 4], 2

출력

[1, 2, 1, 2]

복잡도 분석

위 알고리즘은 각 요소를 정확히 한 번씩만 처리하므로 시간 복잡도는 O(n)입니다(n은 리스트의 길이). 또한 딕셔너리에는 항상 최대 k개의 키만 유지되므로 공간 복잡도는 O(k)입니다. 단순하게 각 윈도우마다 집합(set)을 새로 만들어 계산하는 O(n×k) 방식보다 훨씬 효율적이며, 특히 리스트가 크거나 k가 n에 가까운 경우 그 차이가 두드러집니다.