[ 백준 / C++ ] 2531 : 회전 초밥

[ 문제 ]

 

2531번: 회전 초밥

 

[ 접근방법 ]

 

슬라이딩 윈도우를 통해 O(n) 만에 문제를 해결할 수 있다.

 

(i + k) % n 연산을 통해 인덱스가 n을 넘어 0으로 돌아가는 경우를 쉽게 처리할 수 있다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, d, k, c;
    cin >> n >> d >> k >> c;

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

    vector<int> chk(d + 1, 0);

    int ans = 0, cnt = 0;

    for(int i = 0; i < k; i++){
        if(!chk[vec[i]])cnt++;
        chk[vec[i]]++;
    }
    ans = cnt + (chk[c] ? 0 : 1);

    for(int i = 0; i < n; i++){
        chk[vec[i]]--;
        if(!chk[vec[i]])cnt--;
        if(!chk[vec[(i + k) % n]])cnt++;
        chk[vec[(i + k) % n]]++;

        ans = max(ans, cnt + (chk[c] ? 0 : 1));
    }

    cout << ans;

    return 0;
}