[Sliding Window] 회전 초밥(백준 15961번, 자바)

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

15961번: 회전 초밥

 

문제

1. 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.

입력

• 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. (단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d)

출력

• 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값

구현

1. sliding window 알고리즘을 활용하여 교집합의 정보를 공유하고, 차이 나는 양쪽 끝 원소를 갱신한다.
   • [ 0, 1, 2, 3 ] ⇒ [ 1, 2, 3, 4 ]: 인덱스 0의 초밥 개수 반영 x , 4번 초밥의 개수를 반영한다.
   • visit[N]: N번 초밥의 개수 기록 / cnt: 초밥의 가짓수
2. 쿠폰은 항상 포함되어야 하기 때문에 개수를 미리 증가시킨다.
3. N개의 초밥 ⇒ [0,1,2,3] ~ [N-1, 0,1,2] 의 범위를 고려한다.

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

public class Main{

	static int N,d,k,c;
	static int num[];
	
	public static void main(String[] args) throws IOException {
		
		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());
		
		num=new int[N];
		int answer=Integer.MIN_VALUE;
		for(int i=0;i<N;i++) {
			num[i]=Integer.parseInt(br.readLine());
		}
		int[] visit=new int[d+1];
		int cnt=0;
        
        //쿠폰으로 제공하는 초밥	
		visit[c]=1;
		cnt++;
		
		//0 - k 인덱스의 초밥 cnt 계산  
		for(int i=0;i<k;i++) {	
			if(visit[num[i]]==0) cnt++;
			visit[num[i]]++;
		}
		answer=cnt;
		
	 //시작 인덱스 1 ~ N-1까지 cnt 계산
		for(int i=1;i<=N-1;i++) {
			
			if(visit[num[i-1]]==1 ) cnt--;
			visit[num[i-1]]--;
			
			if(visit[num[(i+k-1)%N]]==0) cnt++;
			visit[num[(i+k-1)%N]]++;
			
			answer=Math.max(cnt, answer);
		}
		System.out.println(answer);
	}
}