[Java] BOJ15961_회전초밥

www.acmicpc.net/problem/15961

15961번: 회전 초밥

---

꽤나 시간이 빡빡한 문제이다.

초밥을 선택할 때 중복되는 부분이 많으므로, 예제 1의 경우

위와 같이 탐색을 할 것이다. 이런 방법을 슬라이딩 윈도우라고 한다.

회전초밥 테이블이 원형이기 때문에 '25' 같은 경우 앞에 있는 [7, 9, 7]과 연결되어 탐색해야 한다.

따라서 탐색을 더 쉽게 하기 위해 앞에서부터 K-1개의 값들을 배열에 더 추가해줬다.

최종적으로 배열은 [7, 9, 7, 30, 2, 7, 9, 25, 7, 9, 7]이 된다.

 

현재 보고 있는 범위에서 초밥 종류가 몇 개 있는지 알 수 있는 배열을 count로 선언했다. 초밥 종류가 중복되기 때문에 개수를 세기 위하여 int 배열로 선언했다.

이 count 배열에서 값이 0이 아닌 수들의 개수가 현재 범위의 초밥 종류의 개수이다.

쿠폰의 경우 count 배열에서 쿠폰번호에 해당하는 수가 0일 경우(현재 범위에 쿠폰 초밥이 없는 경우) 초밥 종류의 개수에 1을 추가해준다.

 

배열은 이전 초밥을 하나 빼고 다음 초밥을 하나 추가하는 식으로 탐색한다.

예제 1의 경우 [7, 9, 7, 30]에서 맨 앞 7을 빼고 다음에 오는 2를 추가하여 [9, 7, 30, 2]를 탐색한다. 이때 count배열을 신경 써주면 된다.

 

맨 앞 초밥을 뺐을 경우 그 초밥의 count가 0이 된다면 초밥 종류의 개수를 하나 빼주고 다음 초밥을 추가할 경우 그 초밥의 count가 1이 된다면 초밥 종류의 갯수를 하나 증가시켜준다. 이때 주의할 점은 빼는 초밥과 추가하는 초밥의 종류가 같은 경우에는 변화가 없어야 하는 것이다.

 

쿠폰의 경우 boolean 변수를 하나 두었는데 이는 현재 쿠폰 초밥을 받았는지를 의미한다. 쿠폰초밥을 받은 상태에서 쿠폰 초밥의 수가 0이 아니게 되면 초밥 종류의 갯수를 감소시켜주고 쿠폰초밥을 받지 않은 상태에서 쿠폰초밥의 수가 0이라면 쿠폰초밥을 받아 초밥 종류의 갯수를 증가시켜준다.

이미 쿠폰초밥을 받은 상태에서 쿠폰초밥의 수가 0이라고 해서 초밥 종류의 갯수를 증가시켜주지 않기 위함이다. 이전에 이미 초밥종류의 수를 늘렸기 때문이다.

 

import java.io.*;
import java.util.Arrays;
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[] arr = new int[N+K-1];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		for (int i = N; i < N+K-1; i++) {
			arr[i] = arr[i-N];
		}
		int[] count = new int[D+1];
		int[] res = new int[N];
		for (int i = 0; i < K; i++) {
			count[arr[i]]++;
		}
		for (int i = 0; i <= D; i++) {
			if(count[i] > 0) res[0]++;
		}
		boolean coupon = false;
		if(count[C] == 0) {
			res[0]++;
			coupon = true;
		}
		int max = res[0];
		for (int i = 1; i < N; i++) {
			
			res[i] = res[i-1];
			count[arr[i-1]]--;
			count[arr[i+K-1]]++;
			if(arr[i-1] != arr[i+K-1]) {
				if(count[arr[i-1]] == 0) res[i]--;
				if(count[arr[i+K-1]] == 1) res[i]++;
			}
			
			if(!coupon && count[C] == 0) {
				coupon = true;
				res[i]++;
			} else if(coupon && count[C] != 0) {
				coupon = false;
				res[i]--;
			}
			max = Math.max(max, res[i]);
		}
		System.out.println(max);
	}
}

 

 

[참고]

슬라이딩 윈도우에 대한 설명이 잘 되어있다.

blog.fakecoding.com/archives/algorithm-slidingwindow/

[알고리즘] 슬라이딩 윈도우 알고리즘