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

풀이 아이디어

n개의 접시가 있을 때 연속해서 먹는 접시의 가짓수는 k개이다.
회전 초밥이 순환 큐처럼 보이도록 하기 위해서
회전 초밥을 입력받는 int[] belt를 int[n+k]로 선언했다.
그래서 0~n-1까지의 회전 초밥과 n~n+k-1를 0~k-1로 대응시켜 연속된 벨트처럼 느껴지게 했다.

[1,2,3,4,5]이고 3개를 먹는다면 [1,2,3,4,5,1,2]로 연속된 벨트처럼 느껴지게 했다.

현재까지 먹은 회전초밥의 종류와 가짓수를 저장하는 배열
int[] eatSushi = new int[d+1];를 선언해주고
쿠폰에 해당하는 인덱스를 미리 추가해줬다. eatSushi[c]=1

그리고 처음에 현재 먹을 수 있는 가짓수를 확인할 큐 sushiQ를 선언하고
k개의 초밥이 유지되도록 큐에 초밥을 넣고 빼주면서
먹을 수 있는 가짓수 curDiversity를
현재까지 최대 가짓수인 maxDiversity와 비교해서 갱신해줬다.
이렇게 해주니 시간복잡도 O(n+k)만에 끝이 났다.

풀이 코드

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

public class _2531 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        // 입력 받기 
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 접시의 수: 2 ≤ N ≤ 30,000
        int d = Integer.parseInt(st.nextToken()); // 초밥의 가짓수: 2 ≤ d ≤ 3,000
        int k = Integer.parseInt(st.nextToken()); // 연속해서 먹는 접시의 수: 2 ≤ k ≤ 3,000 (k ≤ N)
        int c = Integer.parseInt(st.nextToken()); // 쿠폰 번호: 1 ≤ c ≤ d

        // 초밥의 종류를 저장할 배열
        int[] belt = new int[n+k];
        for(int i=0;i<n;i++){
            belt[i] = Integer.parseInt(br.readLine());
        }

        // 처음에 먹을 수 있는 초밥의 가짓수를 구한다.
        int[] eatSushi = new int[d+1]; // 종류별로 먹은 초밥의 수
        eatSushi[c]++; // 쿠폰 초밥을 먹은 것으로 처리
        int curDiversity = 1; // 현재 먹을 수 있는 초밥의 가짓수, 쿠폰 미리 더하고 시작
        Queue<Integer> sushiQ = new LinkedList<Integer>();
        for(int i=0;i<k;i++){
            int inputIndex = i+n; // 초밥 벨트에서 n+k까지 붙이기 위해서 
            belt[inputIndex] = belt[i]; // 벨트의 끝에 n+k까지 붙이기

            if(eatSushi[belt[i]] == 0){
                curDiversity++; // 처음 먹는 초밥이면 가짓수 증가
            }
            eatSushi[belt[i]]++; // 먹은 초밥의 수 증가
            sushiQ.add(belt[i]); // 먹은 초밥의 번호를 큐에 저장
        }
        int maxDiversity = curDiversity; // 최대 먹을 수 있는 초밥의 가짓수

        for(int i=k;i<n+k;i++){
            int outSushi = sushiQ.poll(); // 맨 앞에 있는 초밥을 뺀다.
            eatSushi[outSushi]--; // 먹은 초밥의 수 감소
            if(eatSushi[outSushi] == 0){
                curDiversity--; // 먹은 초밥의 수가 0이면 가짓수 감소
            }

            int inSushi = belt[i]; // 새로운 초밥을 먹는다.
            if(eatSushi[inSushi] == 0 && inSushi != c){
                curDiversity++; // 처음 먹는 초밥이면 가짓수 증가
            }
            eatSushi[inSushi]++; // 먹은 초밥의 수 증가
            sushiQ.add(inSushi); // 먹은 초밥의 번호를 큐에 저장

            maxDiversity = Math.max(maxDiversity, curDiversity); // 먹을 수 있는 가짓수 갱신
        }
        System.out.println(maxDiversity); // 최대값 출력
    }
}