자바 [Algorithm] 슬라이딩 윈도우 - 백준 11465 소가 길을 건너간 이유 5

1. 문제

 

2. 접근법

처음엔 누적합 방식으로 접근하려고 했지만 감이 안잡혀 가장 생각나는 슬라이딩 윈도우 방식을 사용했다.

 

[슬라이딩 윈도우를 사용하여 최소 고장난 신호등 개수 계산]

 

• for 루프를 사용하여 구간을 오른쪽으로 한 칸씩 이동하면서 각 구간의 고장난 신호등 수를 계산
• 새로운 요소를 더하고, 이전 요소를 뺀다
• 현재 구간의 고장난 신호등 수를 min_count와 비교하여 최소값을 갱신

 

3. 코드

package week08;

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

public class Baek14465 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken()); //신호등 개수
        int K = Integer.parseInt(stringTokenizer.nextToken()); //신호등 있어야될 개수
        int B = Integer.parseInt(stringTokenizer.nextToken()); //신호등 번호

        int[] arr = new int[N+1];


        for (int i = 0; i<B; i++){
            int a = Integer.parseInt(bufferedReader.readLine());
            arr[a] = 1;
        }

        int count = 0;

        for (int i = 1; i <= K; i++) {
            count += arr[i];
        }

        int min_count = count;

        for (int i = K+1; i <= N; i++) {
            count += arr[i] - arr[i-K];
            min_count = Math.min(min_count, count);
        }

        System.out.println(min_count);


    }
}