• 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d
  • 시간 복잡도를 O(N)에 종료해야함
• 연속된 구간에서 몇 종류의 초밥이 존재하는지 구하는게 목표
• 따라서, 슬라이딩 윈도우를 통해 연산

• 첫 답안
• 연결을 위해서, 입력으로 주어지는 배열에다 k-1개의 요소를 붙여줘야함.
  • 그래야지 가능한 모든 윈도우 탐색 가능

n, d, k, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.extend(arr[:k])

for i in range(n): 
    subArr = arr[i:i+k]
    currentCnt = len(set(subArr))
    
    if c not in subArr:
        currentCnt += 1
        
    cnt = max(cnt, currentCnt)

print(cnt)

• 시간 초과 발생
• O(NK)의 복잡도
• arr를 set으로 변환하는 과정에서 O(K)의 연산이 매번 수행

• 수정안
• 초밥의 번호를 키로 가지는 딕셔너리 추가
  • 벨류는 초밥의 개수

from collections import defaultdict

n, d, k, c = map(int, input().split())
arr = [int(input()) for _ in range(n)]
arr.extend(arr[:k])

cnt_dict = defaultdict(int)

for i in range(k):
    cnt_dict[arr[i]] += 1
cnt_dict[c] += 1

max_cnt = len(cnt_dict)

for i in range(n):
    cnt_dict[arr[i]] -= 1  
    if cnt_dict[arr[i]] == 0:
        del cnt_dict[arr[i]]

    cnt_dict[arr[i + k]] += 1 

    max_cnt = max(max_cnt, len(cnt_dict))

print(max_cnt)

• 딕셔너리 활용해서 O(1)로 개선
  • 키: 초밥의 종류 / 벨류: 현재 윈도우에 존재하는 개수
  • 최종적으로 딕셔너리의 개수만 구하면 답 도출 가능
• 투포인터 변수를 활용할 수도 있지만, 어차피 for문 내부에서 i, i+k라는 인덱스가 고정적으로 사용되기 때문에 굳이 변수로 선언하지는 않음