첫 시도
- N이 3 * 10^6이므로 완전 탐색은 불가능
- 투 포인터를 사용해서 구현 시도
- 잘 생각해 보니 연속으로 먹는 초밥 갯수를 입력받음
- 먹는 갯수가 정해져 있다면 슬라이딩 윈도우가 최적
- 슬라이딩 윈도우 구현이 미숙해 1시간 초과
해결
- 슬라이딩 윈도우 배열인 choice를 생성, 초기화
- 처음부터 마지막까지 탐색하면서 choice 배열 내부에 있는 초밥의 가짓수를 매번 확인
- % N으로 배열 범위 초과 시 처음으로 돌아가게 해 벨트 구현
- 쿠폰 적용 후 기존 최댓값과 비교
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
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[] choice = new int[D+1]; // 선택된 D개의 초밥
int[] input = new int[N]; // 벨트
int max = 0; // 지금까지 초밥 가짓수의 최댓값
int count = 0; // 현재 choice 배열의 초밥 가짓수
for (int i = 0; i < N; i++) {
input[i] = Integer.parseInt(br.readLine());
}
for(int i = 0; i<K; i++){ // choice 배열 초기화
if(choice[input[i]] == 0) count++;
choice[input[i]]++;
}
for(int i = 1; i < N; i++){
choice[input[i-1]]--;
if(choice[input[i-1]]==0) count--;
if(choice[input[(i+K-1)%N]] == 0) count++; // % N으로 마지막과 시작을 연결
choice[input[(i+K-1)%N]]++;
if(choice[C] == 0) { // 쿠폰 사용
choice[C]++;
count++;
}
max = Math.max(max,count);
}
System.out.println(max);
}
}