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

 

🔒 문제

2531번: 회전 초밥

 

🔑 알고리즘

슬라이딩 윈도우

 

💡  풀이

 

연속적인 값들을 탐색하므로 투 포인터와 슬라이딩 윈도우 알고리즘으로 풀 수 있을 것이라 생각하였다.

k가 고정적인 값으로 주어지므로 슬라이딩 윈도우를 사용하였다.

 

1. 초밥의 번호를 인덱스로 해당 초밥 번호의 먹은 개수를 저장할 크기 d+1의 int형 배열을 만든다.

	int[] eatCount = new int[d+1];

 

2. 0부터 N까지 i 번째부터 i+(k-1) 번째의 초밥을 먹은 것으로 체크하고 몇 종류인지 센다.

for (int i = 0; i < k; i++)
	if(++eatCount[arr[i]] == 1)
		count++;
                
int max = count;

 

i 번째 초밥을 먹지 않은 것으로 하고 i + k 번째 초밥을 먹은 것으로 한다.

 

이때 i번째 초밥을 먹은 수가 0이 되면 해당 종류의 초밥을 먹지 않은 셈이므로 먹은 초밥의 종류의 수를 하나 감소시킨다.

if(--eatCount[arr[i]] == 0)
	count--;

 

또한 i+k번째 초밥을 먹은 수가 1이 되면 처음 해당 종류의 초밥을 먹은 셈이므로 먹은 초밥의 종류의 수를 하나 증가시킨다. 이때 초밥은 회전 초밥으로 k 번 초밥 다음 초밥은 0번째 초밥이 되어야하므로 i+k 를 n으로 나눈 나머지를 인덱스로 한다.

if(++eatCount[arr[(i+k) % N]] == 1)
	count++;

 

쿠폰에 쓰여있는 종류의 초밥을 먹지 않았다면 해당 초밥을 먹을 수 있으므로 먹은 초밥의 종류를 1 증가시킨다.

쿠폰의 초밥까지 갯수를 센 후 먹은 초밥의 종류를 max 값과 비교해 갱신한다.

 

 

 

✏️ 코드

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 = 0;
		int[] arr = new int[N];
		int[] eatCount = new int[d+1];

		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());
			arr[i] = num;
		}

		for (int i = 0; i < k; i++) {
			if(++eatCount[arr[i]] == 1) {
				count++;
			}
		}
		int max = count;

		
		for (int i = 0; i < N; i++) {
			
			if(--eatCount[arr[i]] == 0)
				count--;
			
			if(++eatCount[arr[(i+k) % N]] == 1)
				count++;
			
			if(eatCount[c] == 0)
				max = Math.max(max, count+1);
			else 
				max = Math.max(max, count);
		}

		System.out.println(max);
	}
}