[boj2531, 15961/Java] 회전 초밥

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

2531번: 회전 초밥

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

15961번: 회전 초밥

 

초밥 맛있겠다~~

 

해당 문제에서 주어지는 조건은 

N: 회전 초밥 벨트에 놓인 접시의 수

d: 초밥의 가짓수

k: 연속해서 먹는 접시의 수

c: 쿠폰 번호

이렇게 4가지가 있다.

 

초밥의 가짓수는 N보다 클수도, 작을수도 있다. -> 초밥의 가짓수와 벨트에 놓인 초밥을 관리하는 배열은 따로 둬야 함.

그래서 벨트에 놓인 초밥은 sushi로, 초밥의 가짓수 별로 먹은 여부는 visited로 관리한다.

또한 count를 통해 먹은 초밥 가짓수를 확인한다.

 

일단 k개의 연속된 초밥은 무조건 먹는다고 치고, 초기 count를 구한다.

그리고 max 값을 초기 count로 설정한 뒤 시작점부터 슬라이딩 윈도우 방식과 같이

옆으로 한칸씩 밀어가면서 앞에 먹은 초밥은 빼고, 그 다음 칸의 초밥을 먹는걸로 하면서 count를 업데이트 한다.

이때 카운트를 업데이트 하는 경우는 먹은 초밥의 종류가 바뀔 때만 업데이트를 해야하므로

visited가 0이 될 때, 또 넣고자하는 초밥이 visited가 0일 때만 업데이트 한다.

 

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, d, k, c;
		
		n = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		int[] sushi = new int[n];
		int[] visited = new int[d+1];
		
		for(int i = 0; i<n; i++) {
			sushi[i] = Integer.parseInt(br.readLine());
		}
		
		int count = 0;
		for(int i = 0; i<k; i++) {
			if(visited[sushi[i]] == 0) {
				count++;
			}
			visited[sushi[i]]++;
		}
		
		int max = count;
		
		for(int i = 0; i<n; i++) {
			if(max <= count) {
				if(visited[c] == 0) {// 쿠폰 안먹음
					max = count + 1;
				}
				else {
					max = count;
				}
			}
			
			visited[sushi[i]]--;
			if(visited[sushi[i]] == 0) count--;
			
			if(visited[sushi[(i+k)%n]]==0) count++;
			visited[sushi[(i+k)%n]]++;
			
//			for (int j : visited) {
//				System.out.print(j);
//			}
//			System.out.println();
		}
		
		System.out.println(max);
	}

}