[Java] 백준 / 소가 길을 건너간 이유 5 / 14465번

[Java] 백준 / 소가 길을 건너간 이유 5 / 14465번

문제

소가 길을 건너간 이유 5 문제 링크

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

10 6 5
2
10
1
5
9

출력

1

접근 방식

고장난 신호등 배열에 연속된 K크기씩 처음부터 검사하여 내부에 고장난 신호등을 카운트해서 가장 낮을 때를 출력한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//url : https://www.acmicpc.net/problem/14465

public class Main_S2_14465 {

	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 K = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		boolean[] lightsOff = new boolean[N+1];
		
		for(int i=0;i<B;i++) {
			lightsOff[Integer.parseInt(br.readLine())] = true;
		}
		
		
		int answer = 100000;
		int cnt = 0;
		
		int l = 1;
		int r = K;
		
		for(int i=l;i<=K;i++) {
			if(lightsOff[i]) cnt++;
		}
		
		l++;
		r++;
		
		for(;l<=N-K+1;l++,r++) {
			if(lightsOff[l-1] && !lightsOff[r]) {
				cnt--;
			}
			else if(!lightsOff[l-1] && lightsOff[r]){
				cnt++;
			}
			
			answer = Math.min(answer, cnt);
		}
		
		System.out.println(answer);
		
	}

}