• 슬라이딩 윈도우 방법
  • 처음 K만큼 고장난 신호등의 개수를 센다.
  • 우측의 원소를 포함시키고 좌측의 원소를 제거하면서 K의 범위를 계속 지켜나간다.
  • 포함시킬 우측의 원소가 고장난 상태라면 1을 더하고, 좌측의 원소가 고장난 상태면 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



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

public class Main {
	static int N, K;
	static boolean[] board;

	static int solution() {
		int res = 0, sum = 0;
		for (int i = 1; i <= K; i++)
			if (board[i]) sum++;

		res = sum;
		for (int cur = K+1, prev = 1; cur <= N; cur++, prev++) {
			if (board[prev]) sum--;
			if (board[cur]) sum++;
			res = Math.min(res, sum);
		}
		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());
		K = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());

		board = new boolean[N+1];
		for (int i = 0; i < B; i++) {
			int num = Integer.parseInt(in.readLine());
			board[num] = true;
		}
		System.out.println(solution());
	}
}