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

문제

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

 

접근 방법

1. 정상적으로 작동하는 연속 K의 신호등이 존재하려면 최소 몇개의 신호등을 수리해야하는지 구하는 문제이다.
2. 브루트포스로도 가능하지만 시간초과가 발생한다.
3. 따라서 투포인터로 시간을 줄일 수 있다.
4. 연속하는 구간이 고정되어 있으므로 슬라이딩 윈도우 기법을 사용한다.

코드

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

public class Main {
    private static StringBuilder sb;
    private static BufferedReader br;
    private static StringTokenizer st;
    private static int N,K,B;
    private static boolean[] arr;
    private static int count = 0;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        arr = new boolean[N+1];
        
        for(int i = 1 ; i <=B ; i++){
            arr[Integer.parseInt(br.readLine())] = true;
        }
    }

    //실행
    public static void process() {
        for(int i = 1 ; i <=K ; i++){
            if(arr[i]) count++;
        }

        int s = 1;
        int e = K;

        int min = Integer.MAX_VALUE;

        while(e<N){
            if(arr[s] && !arr[e+1]){
                count--;
            }else if(!arr[s] && arr[e+1]){
                count++;
            }
            min = Math.min(min,count);
            s++;
            e++;

        }

        System.out.println(min);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}