백준 2531번 : 회전초밥 [Java]

문제

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

 

코드

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

public class Main_2531 {

	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[] sushi = new int[n];
		for(int i = 0; i < n; i++) {
			sushi[i] = Integer.parseInt(br.readLine());
		}
		
		boolean[] eatCheck = new boolean[d + 1];
		int answer = -1;
		int count = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < k; j++) {
				if(!eatCheck[sushi[(i + j) % n]]) {
					eatCheck[sushi[(i + j) % n]] = true;
					count++;
				}
			}
			if(!eatCheck[c]) {
				answer = Math.max(answer, count + 1);
			}
			answer = Math.max(answer, count);
			eatCheck[sushi[i]] = false;
			count--;

		}
		System.out.println(answer);
	}

}

 

접근 방법

초밥 가짓수인 d만큼 check할 boolean배열을 만든다.

초밥 배열을 순차적으로 탐색하면서 해당 접시를 첫번째로 먹는다고 가정한다.

배열 크기가 넘어가는 것을 고려해서 i + j % n으로 인덱스 계산을 해준다.

먹은 접시를 true로 바꿔준다.

true인 개수를 세고 false로 바꾸면서 만약 쿠폰부분이 false라면 개수 + 1을 해서 최대값을 찾는다.

 

시행 착오

true인 개수를 세는 행위가 시간이 오래 걸릴 것 같아서

어차피 한칸식 슬라이딩 윈도우처럼 미는 형태이기 때문에 첫번째 접시 부분을 제외한 n -1개는 변하지 않는 다는 점을 이용하기로 했다.

그럼 첫번째 접시만 false로 변경해주고 count를 1감소 시킨다.

개수를 셀 때는 false -> true인 경우만 count를 증가하는 식으로 계산했다.

---

쿠폰 부분이 false일 때 count를 1증가 해주는 방향으로 했더니 테케 1번에서 count가 계속해서 증가하는 현상이 발생했다.

쿠폰을 사용할 수 있는 경우라면 +1을 한 뒤 break를 해주었다.

이렇게 할 경우 또 하나의 반례를 마주한게

어떤 상태에서 쿠폰을 사용할 수 있는 첫번째 경우가 반드시 최대값이 아닐 수도 있다는 사실을 놓쳤다.

그래서 위와 같이 코드를 고쳐주었고 해결되었다.