백준 15961 회전 초밥

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

#include <iostream>
#include <vector>


using namespace std;

int sushi[3001];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, d, k, c;
    int ans = 0;

    cin >> n >> d >> k >> c;

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int s = 0;
    int e = k - 1;



    int cnt = 0;

    for (int i = s; i <= e; i++) {
        if(!sushi[arr[i]]) {
            cnt++;
        }
        sushi[arr[i]]++;
    }

    if (!sushi[c]) {
        ans = cnt + 1;
    } else {
        ans = cnt;
    }

    do {

        if (--sushi[arr[s]] == 0) {
            cnt--;
        }
        s = (s + 1) % n;
        e = (e + 1) % n;
        if (sushi[arr[e]]++ == 0) {
            cnt++;
        }

        if (!sushi[c]) {
            ans = max(ans, cnt + 1);
        } else {
            ans = max(ans, cnt);
        }


    } while (s != 0);


    cout << ans;

    return 0;
}

 슬라이딩 윈도우 문제이다.

 윈도우 안에 연속으로 먹는 초밥의 종류를 저장하고, 하나씩 이동시켜가면서 초밥의 종류의 수를 갱신시키며 풀 수 있다.

 

 윈도우 초기화

    int s = 0;
    int e = k - 1;


    int cnt = 0;

    for (int i = s; i <= e; i++) {
        if(!sushi[arr[i]]) {
            cnt++;
        }
        sushi[arr[i]]++;
    }

    if (!sushi[c]) {
        ans = cnt + 1;
    } else {
        ans = cnt;
    }

 

 k 개의 초밥을 연속으로 먹어야 하므로 입력받은 초밥의 처음부터 k 개의 초밥을 센다. sushi는 현재 윈도우에 있는 초밥의 개수를 뜻하고, 이 값이 0이면 새로운 종류의 초밥을 먹는다는 뜻이므로 cnt에 반영한다. 

 연산이 끝나고, 쿠폰으로 주어지는 초밥을 먹지 않았다면 종류를 더하고, 아니면 그대로 반영한다.

 윈도우 이동

    do {

        if (--sushi[arr[s]] == 0) {
            cnt--;
        }
        s = (s + 1) % n;
        e = (e + 1) % n;
        if (sushi[arr[e]]++ == 0) {
            cnt++;
        }

        if (!sushi[c]) {
            ans = max(ans, cnt + 1);
        } else {
            ans = max(ans, cnt);
        }


    } while (s != 0);

 

 포인터 s가 한 바퀴 돌아 제자리로 돌아갈 때 까지 윈도우를 한 칸씩 이동한다. 앞의 초밥이 빠졌을 때 해당 종류가 없어진다면 cnt--, 뒤의 초밥이 더해졌을 때 초밥의 종류가 추가된다면 cnt++ 하여 종류를 반영한다. 이후, 행사에 참여하여 준 쿠폰에 적힌 초밥을 먹지 않았다면 cnt+1하여 반영하고, 먹었다면 그대로 반영한다.

 

 이렇게 하여 ans에 저장된 값을 출력하여 답을 구할 수 있다.