• boj-2531, jungol-2577과 동일한 문제
  • sliding window 적용
  • 문제에서 의미하는 것을 정확히 해석해내지 못해 시간을 허비했다.
    • 근데, '만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다'라는 문장이 좀 어색한 탓도 있다고 생각한다..
  • 처음에는 K 범위의 바로 바깥쪽 두 곳 중 한 곳에라도 쿠폰에 적혀진 초밥이 있으면 가짓수에 1을 더했는데, 잘못된 방법이다.
  • 2 번째로는 전체 주어진 초밥들 중 쿠폰에 적혀진 초밥이 없다면 N을 늘리고 쿠폰에 적혀진 초밥을 하나 추가해주었는데, 이 또한 잘못된 방법이다.
  • K 범위에 쿠폰에 적혀진 초밥이 없으면 요리사에게 해당 초밥을 요청하면 되므로 현재 가짓수에 1을 더한 값으로 최댓값을 비교한다


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



import java.io.*;
import java.util.*;

public class Main {
	static int N, D, K, C;
	static int[] input, cnt;

	static int solution() {
		int res = 0, sum = 0;
		for (int i = 0; i < K; i++)
			if (++cnt[input[i]] == 1) sum++;
		res = sum + (cnt[C] == 0? 1 : 0);

		for (int cur = K, prev = 0; cur < N+K; cur++, prev++) {
			if(--cnt[input[prev]] == 0) sum--;
			if(++cnt[input[cur]] == 1) sum++;
			res = Math.max(res, sum + (cnt[C] == 0? 1 : 0));
		}
		return res;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer 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());

		input = new int[N + K+1];
		cnt = new int[D+1];
		for (int i = 0; i < N; i++)
			input[i] = Integer.parseInt(in.readLine());
		for (int i = 0; i < K; i++)
			input[N+i] = input[i];

		System.out.println(solution());
	}
}