[백준] 15961번 - 회전 초밥

https://www.acmicpc.net/problem/15961

# 회전 초밥
from collections import defaultdict
N, d, k, c = map(int, input().split())
arr = [int(input()) for _ in range(N)]
arr += arr[:k-1]

left, right = 0, k
result = 0
dict = defaultdict(int)
dict[c] += 1

for x in arr[left:right]:
    dict[x] += 1

while right < len(arr):
    result = max(result, len(dict))
    dict[arr[left]] -= 1
    dict[arr[right]] += 1
    if dict[arr[left]] == 0:
        dict.pop(arr[left])
    left += 1
    right += 1

print(result)

 

투포인터, 슬라이딩 윈도우
1. 입력을 받고 arr을 k만큼 더 이어준다.
2. left와 right의 간격을 k만큼 주고 딕셔너리를 정의한 후 c를 항상 포함
3. 맨 처음 k개만큼을 딕셔너리에 포함
4. 투 포인터(슬라이딩 윈도우)
    - dict의 최대 길이로 result를 초기화
    - dict에 왼쪽 값을 빼주고 오른쪽 값을 더해주기
    - 빼준 왼쪽 값이 0이면 딕셔너리에서 제거
    - left와 right 모두 1씩 증가
5. result 출력

 

딕셔너리의 길이는 key의 개수이다.

따라서 딕셔너리가 포함하는 1 이상의 값들의 개수 (0이 되면 삭제)

해당 키의 개수를 기록하고 총 키의 개수를 구하는 것이다.

이러한 기법을 투 포인터 중 슬라이딩 윈도우라고 한다.

 

딕셔너리 말고 일반 리스트를 이용해서도 구현 가능하다.

다만 각 값이 0인 리스트의 길이를 k만큼 미리 정의해두고

길이로 접근하지 않고 0이 아닌 값들의 개수로 접근을 해야 한다.