[15961] 회전 초밥

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

15961번: 회전 초밥

 

문제 해결 방법

슬라이딩 윈도우를 사용해 구현했다.

처음 k개를 먹고 쿠폰 처리를 안 할 경우 답이 제대로 나오지 않지만, 맞았다고 뜬다. 이 부분에 대한 테스트 케이스가 없는 것 같다.

 

 

import java.util.*;

public class Main {
    static int N, d, k, c;
    static int[] sushi;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        d = sc.nextInt();
        k = sc.nextInt();
        c = sc.nextInt();
        sushi = new int[N];

        for (int i = 0; i < N; i++) {
            sushi[i] = sc.nextInt();
        }

        int cnt = 0;
        int[] D = new int[d + 1];
        for (int i = 0; i < k; i++) {
            if (D[sushi[i]] == 0) cnt++;
            D[sushi[i]]++;
        }

        int max = cnt;
        if (D[c] == 0) max++;

        for (int i = 1; i < N; i++) {
            D[sushi[i - 1]]--;
            if (D[sushi[i - 1]] == 0) cnt--;

            D[sushi[(i + k - 1) % N]]++;
            if (D[sushi[(i + k - 1) % N]] == 1) cnt++;

            int coupon = (D[c] == 0) ? 1 : 0;
            max = Math.max(cnt + coupon, max);
        }

        System.out.println(max);
    }
}