[백준] 15961. 회전 초밥 (Java)

[BOJ] 15961. 회전 초밥

📌 풀이 과정

윈도우를 한 칸씩 오른쪽으로 이동시키면서, 왼쪽 끝의 초밥을 제거하고 오른쪽 끝의 초밥을 추가한다.
이 과정에서 초밥 종류도 갱신 해야한다.

매번 윈도우 이동 후, 쿠폰으로 제공되는 초밥이
윈도우에 포함되지 않는 경우를 고려해 최대 종류 수를 갱신해야 한다.

이 아이디어가 떠올랐지만 바로 코드로 작성하지 못한 점이 아쉽다!!
[BOJ] DNA 비밀번호 문제에서도 비슷한 아이디어를 다뤘던 기억이 났다.

✨ 제출 코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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[] count = new int[d + 1];
		int[] sushi = new int[N];
		
		for(int i = 0; i < N; i++) {
			sushi[i] = Integer.parseInt(br.readLine());
		}
		
		int type = 0;
        // 초기 윈도우 설정하기
		for(int i = 0; i < k; i++) {
			if(count[sushi[i]] == 0) {
				type++; // 처음 카운팅하는 종류일 경우에만
			}
			count[sushi[i]]++; 
		}
		
		int ans = type;
		for(int start = 0; start < N; start++) {
			int end = (start + k) % N;
			
			// 왼쪽 초밥 제거
			if(count[sushi[start]] == 1) type--;
			
			count[sushi[start]]--;
			
			// 오른쪽 초밥 추가
			if(count[sushi[end]] == 0) type++;
			
			count[sushi[end]]++;
			
			// 쿠폰 초밥 포함한 최대 종류 수 갱신
			int maxType = type;
			if(count[c] == 0) maxType++;
			
			ans = Math.max(ans, maxType);
			
		}
		
		System.out.println(ans);
	}

}