이번에 풀어본 문제는
백준 15961번 회전 초밥 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 [] belt = new int[N + k];
        for (int i = 0; i < N; i++) {
            belt[i] = Integer.parseInt(br.readLine());
        }

        int [] count = new int[d + 1];
        int tmpCount = 0;
        for (int i = 0; i < k; i++) {
            // k개 만큼 뒤에 붙여줌 (배열 범위를 벗어난 윈도우를 계산하기 위해)
            belt[i + N] = belt[i];

            // 첫 번째 윈도우 세팅
            if (count[belt[i]] < 1) tmpCount++;
            count[belt[i]]++;
        }
        int answer = tmpCount;

        // 슬라이딩
        for (int i = 1; i < N; i++) {
            // start
            count[belt[i - 1]]--;
            if (count[belt[i - 1]] < 1) tmpCount--;

            // end
            int end = i + k - 1;
            // 아직 안먹었으면 카운트++
            if (count[belt[end]] < 1) tmpCount++;
            count[belt[end]]++;
            // 쿠폰 초밥 안먹었으면 + 1
            answer = count[c] < 1 ? Math.max(answer, tmpCount + 1) : Math.max(answer, tmpCount);
        }

        System.out.print(answer);
    }
}

📝 풀이

연속된 k개의 초밥을 선택하며, c 번호의 초밥이 무료로 주어집니다.
가장 다양한 초밥을 먹을 수 있는 경우를 구하는 문제입니다.
고정된 k 범위 만큼의 초밥을 선택하여 가장 많은 경우를 구하는 문제이므로, 슬라이딩 윈도우를 사용했습니다.
회전하는 벨트이기 때문에 뒤쪽 인덱스를 초과하는 범위까지 판단해야 합니다. 따라서 편의상 belt 배열에 k만큼의 값을 덧붙이고 시작했습니다.
count 배열의 인덱스는 초밥의 번호를 의미하며, 값은 먹은 개수입니다. 이 값을 토대로 중복해서 먹은 초밥이 있는지 여부를 판단합니다.
매 반복마다 answer 값을 비교해주고, 쿠폰으로 받을 초밥을 아직 먹지 않았다면 1을 더한 값과 비교해줍니다.