문제 개요
정수 리스트 nums와 정수 k가 주어집니다. 우리는 리스트 안의 어떤 숫자든 다른 값으로 바꿀 수 있는 연산을 최대 k번까지 수행할 수 있습니다. 이때, 모든 원소가 동일한 숫자로 채워진 가장 긴 연속 하위 목록(부분 배열)의 길이를 구하는 것이 목표입니다.
예를 들어, nums = [8, 6, 6, 4, 3, 6, 6]이고 k = 2라고 가정해 보겠습니다. 이 경우 정답은 6입니다. 값이 4와 3인 두 원소를 6으로 바꾸면 [8, 6, 6, 6, 6, 6, 6]이 되어, 숫자 6이 연속으로 6번 등장하기 때문입니다.
접근 방법: 슬라이딩 윈도우
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 윈도우 내에서 가장 자주 등장하는 숫자의 빈도(max_count)를 추적합니다.
- 윈도우 길이에서 max_count를 뺀 값이 k보다 크다면, 해당 윈도우를 모두 같은 숫자로 만들 수 없으므로 왼쪽 끝을 한 칸 줄입니다.
- 윈도우가 한 번 늘어난 후 다시 줄어들지 않는 특성 덕분에 각 원소를 한 번씩만 방문하여 O(n) 시간 복잡도로 해결할 수 있습니다.
알고리즘 단계
- nums가 비어 있으면 0을 반환합니다.
- 숫자 빈도를 저장할 맵 num_count, 최대 빈도 max_count, 윈도우 시작 인덱스 start를 초기화합니다.
- enumerate로 각 인덱스 end와 값 num을 순회하면서:
- num_count[num]을 1 증가시키고, max_count를 현재 빈도와 비교해 갱신합니다.
- 윈도우 길이(end − start + 1)가 max_count + k보다 크면, 왼쪽 끝 숫자의 빈도를 1 감소시키고 start를 1 증가시킵니다.
- 순회가 끝나면 end − start + 1을 반환합니다.
구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
from collections import defaultdict
def solve(nums, k):
if not nums:
return 0
num_count = defaultdict(int)
max_count = 0
start = 0
for end, num in enumerate(nums):
num_count[num] += 1
max_count = max(max_count, num_count[num])
if end - start + 1 > max_count + k:
num_count[nums[start]] -= 1
start += 1
return end - start + 1
nums = [8, 6, 6, 4, 3, 6, 6]
k = 2
print(solve(nums, k))입력
[8, 6, 6, 4, 3, 6, 6], 2
출력
6
복잡도 분석
시간 복잡도: O(n) — 각 원소를 정확히 한 번씩만 처리합니다.
공간 복잡도: O(n) — 최악의 경우 모든 숫자가 서로 다를 때 빈도 맵에 n개의 키가 저장될 수 있습니다.