2531번: 회전 초밥

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


$O(n)$

슬라이딩 윈도우 기법을 이용해 추가/제거 되는 초밥에 따라 변하는 초밥 종류 수를 수정해준다.

#include<cstdio>
int n, d, k, c, a[30000], b[3001], cnt = 1, maxi;
int main() {
    scanf("%d%d%d%d", &n, &d, &k, &c);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    b[c]++;
    for (int i = 0; i < k; i++) cnt += !b[a[i]]++;
    for (int i = k; i < n + k; i++) {
        cnt += !b[a[i%n]]++ - !--b[a[i - k]];
        if (cnt > maxi) maxi = cnt;
    }
    printf("%d", maxi);
    return 0;
}