백준[15961] 회전초밥

문제 설명

문제 링크

http://icpc.me/15961

15961번: 회전 초밥

풀이

슬라이딩 윈도우로 풀 수 있다.

k개의 연속된 초밥 그룹에 어떤 종류의 초밥이 몇 개 있는지 그룹을 오른쪽으로 밀면서 그룹에 수들의 종류가 몇 개 있는지 확인하면 된다.

그룹을 밀 때, 기존의 왼쪽 끝의 수가 하나 빠지고, 오른쪽에 수가 하나 들어온다.

이때, 왼쪽 수가 기존의 그룹에 유일하면 cnt--해주고, 새로운 수가 기존에 없으면 cnt++을 하면 된다.

회전하는 수 처리는 원래의 배열 뒤에 앞의 수 k-1개를 넣으면 모든 경우를 확인 할 수 있다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int check[3003];
vector<int> v;

int main() {
    int n, d, k, c; scanf("%d %d %d %d", &n, &d, &k, &c);
    for (int i = 0; i < n; i++) {
        int tmp; scanf("%d", &tmp);
        v.push_back(tmp);
    }
    for (int i = 0; i < k - 1; i++) v.push_back(v[i]);
    int l = 0, r = k - 1, cnt = 0, ans = 0;
    for (int i = 0; i < k; i++) {
        if (!check[v[i]]) cnt++;
        check[v[i]]++;
    }
    if (!check[c]) ans = max(ans, cnt + 1);
    else ans = max(ans, cnt);

    while (r + 1 < v.size()) {
        if (check[v[l]] == 1) cnt--;
        check[v[l]]--; l++;
        if (check[v[++r]] == 0) cnt++;
        check[v[r]]++;
        if (!check[c]) ans = max(ans, cnt + 1);
        else ans = max(ans, cnt);
        printf("%d %d %d\n", l, r, cnt);
    }
    printf("%d", ans);
}