[백준] 2531. 회전 초밥

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

2531번: 회전 초밥

투포인터 문제로 주의할 점은 다음과 같다.

• 최대 초밥 종류의 개수를 구해야하므로, 굳이 k 미만의 접시를 고를 필요가 없으며, 정확히 k개의 접시를 고르면 된다. 즉, 투포인터보다 슬라이딩 윈도우로 푸는 것이 더 적합하다! (start와 end가 함께 이동하며 그 범위가 k로 유지)
• 먹은 초밥을 배열로 관리한다(eat[30] = 1이면, 30번의 초밥을 1개 먹었다는 의미). 종종 이런 경우 자료구조 중 map을 활용하려는 생각이 드는데.. map과 배열 둘 다 적용 가능하다. 단. 배열이 좀 더 깔끔한 거 같으므로 다음부터는 배열을 떠올려보자..!
• 쿠폰 초밥이 벨트 위에 없더라도 요리사가 새로 만들어준다고 문제에 적혀있다. 이걸 못 보고 벨트에 쿠폰 초밥이 없으면 제외시켰다. 항상 문제를 잘 읽고, 문제에 적힌대로 해석하자.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {

        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[] arr = new int[n];
        int[] eat = new int[d + 1];

        int answer = 0;
        int cnt = 0;

        // 0. 초밥 초기화
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 1. 0번째 ~ k-1번째까지 먹고, 먹은 초밥 종류 개수 반영
        for (int i = 0; i < k; i++) {
            eat[arr[i]]++;
        }
        for (int i = 1; i < eat.length; i++) {
            if (eat[i] != 0) cnt++;
        }

        // 2. 슬라이딩 윈도우 시작
        int start = 0;
        int end = k - 1;

        while (true) {
            // 2 - 1. answer 반영
            if (eat[c] != 0) {
                answer = Math.max(answer, cnt);
            } else {
                answer = Math.max(answer, cnt + 1);
            }

            // 2 - 2. start, end 한 칸씩 오른쪽으로 이동

            // 만약 start가 n - 1이라면, 오른쪽으로 이동했을 때 원점이므로 끝내기
            if (start == n - 1) {
                break;
            }

            // start 이동
            eat[arr[start]]--;
            if (eat[arr[start]] == 0) cnt--;
            start++;

            // end 이동
            end = (end == n - 1) ? 0 : end + 1;
            eat[arr[end]]++;
            if (eat[arr[end]] == 1) cnt++;
        }

        System.out.println(answer);
    }
}