[백준] 2531번: 회전 초밥 (Java)

문제 (Silver 1)

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

2531번: 회전 초밥

---

풀이

길이가 k인 슬라이딩 윈도우로 구현하였다.

이 때, 매번 i번째에 대해서 k개를 탐색하는 것이 아니라 ( → 시간초과! )

초기의 window를 셋팅하고 start와 end 인덱스에 대해서만 처리하였다.

슬라이딩 할 때,

eat[start] 값을 -1하고, 그 값이 0이라면 cnt를 하나 감소시킨다.

→ 윈도우 안에 해당 종류의 초밥을 먹는 일이 없으므로

eat[end] 값을 +1하고, 그 값이 1이라면(= 아래 코드에서는 +1 하기전에 0인가를 판단) cnt를 하나 증가시킨다.

→ 이전에 없던 종류의 초밥을 먹는 것이므로

코드

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);
    }
}

제출