[Java Algorithm] 회전 초밥 BOJ #15961

문제

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

15961번: 회전 초밥

 

내 문제 풀이

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

public class Main {
	
	static int n, d, k, c; // 접시 수, 초밥 종류, 연속해서 먹는 접시 수, 쿠폰
	static int susi[], ate[]; // 벨트에 놓인 초밥 종류, 초밥 별 먹은 개수
	static int cnt, ans;
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		susi = new int[n];
		ate = new int[d+1];
		for(int i = 0; i < n; i++) {
			susi[i] = Integer.parseInt(in.readLine());
		}
		
		eat();
		System.out.println(ans);
	}
	
	public static void eat() { // 슬라이딩 윈도우
		for(int i = 0; i < k; i++) {
			if(ate[susi[i]] == 0) ans++;
			ate[susi[i]]++;
		}
		cnt = ans;
		ans = (ate[c] > 0) ? cnt : cnt + 1;
		
		int start = k;
		while(start != n-1+k) {
			if(--ate[susi[(start - k) % n]] == 0) cnt--;
			if(ate[susi[start % n]]++ == 0) cnt++;
			ans = Math.max(ans, (ate[c] > 0) ? cnt : cnt + 1);
			start++;
		}
	}
}

👉 슬라이딩 윈도우 문제

가장 먼저 첫 번째 접시부터 k개의 접시를 먹어주었다. 먹은 초밥은 ate 배열에 표시했고,

만약 해당하는 접시의 초밥이 처음 먹는 초밥일 경우에는 ans 변수를 증가시켜주었다.

 

cnt 변수에 ans 값을 담아놓고, 쿠폰에 해당하는 초밥을 먹었다면 ans를 그대로 놔두었고

쿠폰에 해당하는 초밥을 먹지 않았다면 ans를 1 증가시켰다. (더 많은 종류의 초밥 먹을 수 있음)

 

두 번째 탐색부터는 while을 사용하여 슬라이딩 윈도우 방식을 적용했다.

(start - k) % n 연산을 통해서 한 칸씩 뒤로 당기며 탐색할 수 있도록 하였다.

 

두 개의 if 조건문을 확인해보면,

먹은 초밥  중 첫 번째 초밥을 버리는데, 그 초밥이 더 이상 먹지 않은 초밥이 될 경우 cnt를 감소,

초밥 하나를 새로 먹는데 그 초밥이 먹은적 없는 초밥일 경우에는 cnt를 증가시켰다.

 

마지막으로 ans를 Max 값으로 업데이트 시켜주었고,

start를 증가시켜서 그 다음 초밥을 먹을 수 있도록 해주었으며,

만약 모든 초밥 탐색에 완료했다면 while문을 탈출할 수 있게 했다.

 

💡 피드백

• 슬라이딩 윈도우 문제를 많이 안풀어보기도 했고, 정말 오랜만에 풀어봐서 바로 떠오르지 않았지만
  그렇게 어려운 개념은 아니기 때문에 비슷한 문제들을 몇 번 더 풀어보면 더 익숙히 풀 수 있을 것 같다.