[백준] BOJ 2531 회전 초밥(자바)

문제 풀이

문제를 잘 못 이해해서 오래 걸렸던 문제였다.

 

문제에

'k개의 접시를 연속해서 먹을 경우' 라는 조건이 주어진다. 나는 이 조건에 대해 k개의 다른 종류를 먹어야 한다고 생각했다. 하지만, k개의 연속된 초밥을 먹는다라고 해석해야 한다.

 

또한, 주의해야 할 점이 회전 초밥은 원형이니까 배열 마지막 인덱스부터 다시 시작 인덱스 0 ~ k-1까지의 조합도 생각해야 한다.

 

 

예제 입력 1번을 예시로 설명해 보겠습니다. 25가 배열의 끝입니다. 그런데, 여기서 (25, 7, 9, 7)의 조합도 생각해야 합니다. 

 

 

 

따라서, 다음과 같이 저는 배열의 끝에 k-1만큼 붙였습니다. 그러면 마지막 조합 ( 25, 7, 9, 7)에 대해서도 구해볼 수 있습니다. 

 

 

 

 

 

 

 

---

구현

public class Main_2531 {
	static int result;

	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[] maps = new int[n + k - 1];
		result = Integer.MIN_VALUE;

		for (int i = 0; i < n; i++) {
			maps[i] = Integer.parseInt(br.readLine());
		}

		int j = 0;
        //마지막 조합을 위해 k-1만큼 붙임
		for (int i = n; i < maps.length; i++, j++) {
			maps[i] = maps[j];
		}

		int start = 0, end = k - 1;

		while (start < n && end < maps.length) {
			boolean[] visited = new boolean[d + 1];

			// start~end 사이의 초밥 번호가 중복된 번호가 있는지 확인
			int cnt = 0;
			for (int i = start; i <= end; i++) {
				if (!visited[maps[i]]) {
					visited[maps[i]] = true;
					cnt++;
				}
			}

			// 범위 사이의 초밥 번호가 중복되지 않은 경우
			if (!visited[c]) {
				result = Math.max(result, cnt + 1);
			} else {
				result = Math.max(result, cnt);
			}

			end++;
			start++;
		}

		System.out.println(result);
	}

}