[BOJ]2531号:回転寿司(Java)

質問する (Silver 1)

2531号：回転寿司

に答える

長さkのスライドウィンドウとして表現される.
このとき,i回目にk個ブラウズするたびではない(→タイムアウト!)
初期ウィンドウを設定し、startとendインデックスのみを処理します.

スライド時、

eat[start]値-1、値が0の場合はcntを1つ減らします.
→窓口内ではそれなりの種類のお寿司は食べず、
eat[end]値+1、値が1(=以下のコードは+1の前に0と判断)の場合、cntを1つ追加します.
→以前食べたことのないお寿司を食べていたので

コード#コード#

package implement;

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

public class BOJ_2531_회전초밥 {
    static int N, d, k, c;
    static int[] sushi;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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())-1;
        sushi = new int[N];
        int[] eat = new int[d];	// 해당 종류의 초밥을 몇개 먹었는지 저장하는 배열
        for(int i =0 ; i < N ; i++){
            sushi[i] = Integer.parseInt(br.readLine())-1;
        }
        int res = 0;
        int cnt = 0;
        for(int i =0 ; i < k ; i++){
            if(eat[sushi[i]]++ == 0) cnt++;
        }
        for(int i =0 ; i < N ; i++){
            if(res <= cnt){     // MAX 값 새로 갱신
                if(eat[c] == 0) res = cnt+1;
                else res = cnt;
            }
            int j = (i+k)%N;  // end 값 (순환 → 인덱스 초과할 때의 처리)
            if(eat[sushi[j]] ++ == 0) cnt++;
            if(-- eat[sushi[i]] == 0) cnt--;
        }
        System.out.println(res);
    }
}

送信