문제 소개
숫자로 이루어진 리스트 nums와 정수 k가 주어졌을 때, 정확히 k개의 서로 다른(고유한) 숫자를 포함하는 연속된 부분 리스트(sublist)의 개수를 구해야 합니다.
예를 들어 nums = [2, 2, 3, 4], k = 2라고 한다면, 조건을 만족하는 부분 리스트는 [2, 2, 3], [2, 3], [3, 4]로 총 3개이므로 출력 결과는 3이 됩니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(sliding window) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '정확히 k개'인 경우를 직접 세는 대신, '최대 k개 이하'인 경우의 수에서 '최대 k-1개 이하'인 경우의 수를 빼는 것입니다.
구체적인 풀이 단계는 다음과 같습니다.
- count(K): 최대 K개의 고유 숫자를 포함하는 부분 리스트의 개수를 반환하는 함수를 정의합니다.
- slot := 각 숫자의 등장 횟수를 저장하는 맵(Counter), 기본값은 모두 0
- i := res := 0
- 리스트의 각 인덱스 j와 값 x에 대해 반복:
- slot[x] 값을 1 증가
- slot의 크기(서로 다른 숫자의 개수)가 K보다 커지면 왼쪽 포인터 i를 이동하며 윈도우 축소:
- slot[nums[i]] 값 1 감소
- 값이 0이 되면 해당 키를 맵에서 제거
- i를 1 증가
- res에 현재 윈도우 길이(j - i + 1)를 더함
- res 반환
- 메인 로직에서는 count(k) - count(k - 1)을 반환하여 '정확히 k개'인 경우만 계산
예제 코드 (Python)
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
class Solution:
def solve(self, nums, k):
def count(K):
slot = Counter()
i = res = 0
for j, x in enumerate(nums):
slot[x] += 1
while len(slot) > K:
slot[nums[i]] -= 1
if slot[nums[i]] == 0:
del slot[nums[i]]
i += 1
res += j - i + 1
return res
return count(k) - count(k - 1)
ob = Solution()
nums = [2, 2, 3, 4]
k = 2
print(ob.solve(nums, k))입력
[2, 2, 3, 4], 2
출력
3
복잡도 분석
count 함수 안에서 오른쪽 포인터 j와 왼쪽 포인터 i는 각각 리스트를 최대 한 번씩 순회하므로, count 호출 한 번당 시간 복잡도는 O(n)입니다. count를 두 번 호출하므로 전체 시간 복잡도 역시 O(n)이며, 공간 복잡도는 저장되는 고유 숫자의 개수에 따라 최대 O(n)입니다.