백준 15961 회전 초밥 혼내주기

 

슬라이딩 윈도우로 k개씩 초밥의 종류를 세면서 최대가 되는 종류의 가지수를 출력하면 된다. 처음에 종류를 어떻게 유지할지 떠오르지 않아서 unordered_map을 이용했는데, 그냥 정수형 배열에 유지하는 방식이 속도면에서 훨씬 우월하다.

 

#include <iostream>
#include <deque>
using namespace std;

int arr[3000001];
int sushi[3001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, d, k, c; cin >> n >> d >> k >> c;
    for(int i = 1; i <= n; ++i) cin >> arr[i];

    deque<int> dq;
    int cnt = 0, ans = 0;
    for(int i = 1; i <= k; ++i){
        if(!sushi[arr[i]]) cnt++;
        sushi[arr[i]]++; dq.push_back(arr[i]);
    }

    for(int s = 1, e = k+1; s <= n; ++s, ++e){
        if(e == n+1) e = 1;
        ans = max(ans, sushi[c] ? cnt : cnt+1);
        
        sushi[arr[s]]--; dq.pop_front();
        if(!sushi[arr[s]]) cnt--;

        if(!sushi[arr[e]]) cnt++;
        sushi[arr[e]]++; dq.push_back(arr[e]);
    }
    
    cout << ans;
}