BOJ 15961 회전 초밥

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

15961번: 회전 초밥

 

교육적인 슬라이딩 윈도우 문제입니다. 원형으로 돌면서 $k$짜리 길이의 초밥들을 관리해주면 됩니다. 초밥이 추가될 때마다 visited 값을 늘려주고 초밥이 제거될 때마다 visited 값을 줄여주면 쉽게 구현할 수 있습니다. 쿠폰의 경우, 현재 가지고 있는 초밥 중 $c$번 초밥이 있는지 확인해주면 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

using namespace std;

int T, n, d, k, c, visited[3030];
vector<int> vec;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> d >> k >> c;

    vec.resize(n);
    for (int i = 0; i < n; i++) cin >> vec[i];

    int cnt = 0;
    for (int i = 0; i < k; i++) {
      visited[vec[i]]++;
      if (visited[vec[i]] == 1) cnt++;
    }

    int ans = 0;

    for (int i = k; i < n + k; i++) {
      int in = i;
      int out = i - k;

      visited[vec[in % n]]++;
      if (visited[vec[in % n]] == 1) cnt++;
      visited[vec[out % n]]--;
      if (visited[vec[out % n]] == 0) cnt--;

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

    cout << ans << endl;
  }

  return 0;
}