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

 

문제

15961번: 회전 초밥

 

알고리즘

투 포인터, 슬라이딩 윈도우

 

 

풀이

2531. 회전 초밥 문제에서 N의 개수가 300만으로 100배 늘었다.

따라서 이전 문제를 브루트포스 방식으로 풀었다면 이번 문제에서는 시간 초과가 날 것이다.

 

연속된 k 개의 값들을 한칸씩 전진하며 탐색하는 문제이기 때문에 슬라이딩 윈도우로 문제를 해결한다.

 

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

2. 0 번째부터 (k-1) 번째의 초밥을 먹은 것으로 체크하고 종류를 센다.

3. i번째 초밥을 먹지 않은 것으로 하고, i+k 번째 초밥을 먹은 것으로 변경한다. (한 칸 전진)

4. 쿠폰에 쓰여있는 초밥을 먹지 않았다면 해당 초밥을 추가한다.

5. 몇가지 초밥을 먹었는지 계산하고 최댓값을 갱신한다.

6. 초밥 접시의 개수만큼 3~5를 반복한다.

 

 

코드

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++)
			arr[i] = Integer.parseInt(br.readLine());

		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);
			
			max = Math.max(max, count);
		}

		System.out.println(max);
	}
}