[Java] 백준 15961번 : 회전 초밥

문제

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

 

접근 방법

1. 초밥 접시의 수가 3,000,000개이고 종류가 최대 3000개라서 슬라이드에 대해 for문을 돌면 시간초과가 발생한다.
2. 따라서 포인터를 이용한 슬라이딩 윈도우를 사용하였다. 또한 카운트 배열을 만들어 같은 숫자가 1개일때만 count값이 올라가도록 하였다.

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,D,K,C;
    private static int[] arr;
    private static int[] count;


    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new int[N+K-1];

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

        //(한바퀴 돌경우를 생각하여)맨뒤에서부터 최대 K까지만 앞에있는 수를 넣어준다.
        for(int i = 0 ; i < K-1 ; i++){
            arr[N++] = arr[i];
        }

        count = new int[D+1];
    }

    //실행
    public static void process() {

        int cnt = 0;
        int result = 0;

        for(int i = 0 ; i < N ; i++){
            if(++count[arr[i]]==1) cnt++;
            
            if(i>=K-1){
            
                if(i>=K){
                    if(--count[arr[i-K]]==0) cnt--;
                }

                if(count[C] == 0){
                    result = Math.max(result,cnt+1);
                }else{
                    result = Math.max(result,cnt);
                }
            }
        }

        System.out.println(result);

    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}