[BOJ 백준] 2531번 회전 초밥

문제

BOJ 2531 : https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

접근

 슬라이딩 윈도우(Sliding Window)를 이용하여 문제를 해결하였다. 연속으로 먹을 수 있는 초밥의 개수(k)만큼 윈도우에 담아주고, 윈도우를 한 칸씩 앞으로 밀어가면서 최대의 경우가 되는지 확인해 보는 것이다. 당연히 윈도우를 앞으로 밀고 나갈 때마다 새로 들어오는 초밥은 추가해 주고, 기존에 있던 초밥 하나는 빼주면서 값을 확인해준다. 이때 중요한 것은 배열의 끝까지 봤다고 해서 끝이 아니다. 배열은 선형으로 생겼지만 사실 회전 초밥은 둥근 형태로 끝과 시작이 이어져 있다. 즉, 배열의 크기 + 윈도우의 크기(=k)만큼 더 봐줘야 한다는 사실을 간과하면 안 된다. 또, 이 모든 과정을 시작하기에 앞서 우리는 쿠폰으로 받은 초밥은 연속되지 않아도 먹을 수 있어서 제일 처음에 카운터를 세고 시작해야 한다. 

코드

#include <iostream>

using namespace std;

int main() {
    int n, d, k, c, arr[33005], sushi[3005] = {0}, counter = 0,ans = 0;
    cin >> n >> d >> k >> c;
    sushi[c]++;
    counter++;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (i < k) {
            if (sushi[arr[i]] == 0)
                counter++;
            sushi[arr[i]]++;
        }
    }
    for (int i = 0; i < k; i++)
        arr[n + i] = arr[i];
    ans = counter;
    for (int i = k; i < n + k; i++) {
        if (sushi[arr[i]] == 0)
            counter++;
        sushi[arr[i]]++;
        sushi[arr[i - k]]--;
        if (sushi[arr[i - k]] == 0)
            counter--;
        if (counter > ans)
            ans = counter;
    }
    cout<<ans;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study