그냥 완전탐색 시 이중 for문으로 O(nk)가 되어 시간초과 발생함.
-> 슬라이딩 윈도우 기법을 사용하면 O(n)만에 가능!
다음 구간은 이전 구간에서 1개 빠지고 1개 들어오는 형태로 구현, defaultdict로 종류별 초밥 개수 관리하고, 총 초밥 종류 개수는 len(dict)로 구함
* 슬라이딩 윈도우 사용하는 경우:
- 입력이 리스트(또는 문자열)이고
- 연속된 부분구간(subarray, substring)에서 뭔가를 구하려고 할 때
- 매번 새로 계산하지 말고, 이전 계산을 재사용하면서 효율적으로 풀고 싶을 때
from collections import defaultdict
line = list(map(int, input().split()))
n, d, k, c = line[0], line[1], line[2], line[3]
s_list = []
for _ in range(n):
line = int(input())
s_list.append(line)
s_list.extend(s_list[:k - 1]) # 원형 테이블이므로 맨 뒤에 앞 쪽 일부를 복사해서 연장
dic = defaultdict(int)
# 초기 세팅
for i in range(k):
dic[s_list[i]] += 1
# 쿠폰 추가
dic[c] += 1
max_len = len(dic)
# 슬라이딩 윈도우로 탐색 -> O(n)
for i in range(1, n):
# 맨 뒤 초밥 하나 빼기
dic[s_list[i - 1]] -= 1
if dic[s_list[i - 1]] == 0: # 0이면 삭제
del dic[s_list[i - 1]]
# 새로 초밥 하나 추가
dic[s_list[i + k - 1]] += 1
# 최대 길이 갱신
max_len = max(max_len, len(dic))
print(max_len)