[백준 15961] 회전 초밥(Java)

문제 링크 : https://www.acmicpc.net/problem/15961

이 문제는 슬라이딩 윈도우를 이용하여 풀 수 있습니다. 초밥 가짓수의 최댓값은 연속해서 먹는 접시의 개수에 쿠폰을 더한 값, 즉 k+1이 됩니다. 따라서 k개의 원소를 고정하여 탐색하면서 제거되는 부분을 제거, 새롭게 추가되는 부분을 추가하는 방식으로 구현합니다. 이 때 쿠폰으로 먹을 수 있는 부분을 탐색하여 해당 범위에 없다면 값을 추가하는 방식으로 진행합니다.

이를 위해 check 배열을 int로 설정하여 현재 k 범위 내의 선택된 초밥의 개수를 구합니다. 초기 범위 내의 check 배열을 카운트한 후 뺄 값의 check 배열의 값이 0이라면 카운트를 빼주고, 추가할 값의 check 배열의 값이 0이라면 카운트를 더하는 방식으로 진행합니다. 여기서 주의할 점은 최솟값은 쿠폰을 사용했을 때인 1이기 때문에 초기값을 0이 아닌 1로 설정해주어야 합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N=Integer.parseInt(st.nextToken());
        int d=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        int c=Integer.parseInt(st.nextToken());
        int[] A = new int[N];
        int[] check = new int[d+1];

        for(int i=0;i<N;i++) A[i]=Integer.parseInt(br.readLine());

        int res=1;
        check[c]++;
        for(int i=0;i<k;i++) {
            if(check[A[i]]==0) res++;
            check[A[i]]++;
        }

        int cnt=res;
        for(int i=1;i<N;i++) {
            int pop = A[i-1];
            check[pop]--;
            if(check[pop]==0) cnt--;

            int add = A[(i+k-1)%N];
            if(check[add]==0) cnt++;
            check[add]++;

            res = Math.max(res,cnt);
        }

        System.out.println(res);
    }

}