슬라이딩 윈도우 개념

슬라이딩 윈도우란 투포인터 알고리즘의 일종으로 볼 수 있다.

배열의 구간을 훑지만 일정 구간씩 보는 것이다.

 

0000000000000000 배열이 있을 때

XXX0000000000000

0XXX000000000000

00XXX00000000000

000XXX0000000000

위와 같은 방식으로 일정 구간씩 훌는 것이다.

갯수 세기에 주로 쓰인다.

 

 

 

 

 

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

14465번: 소가 길을 건너간 이유 5

 

 

슬라이딩 윈도우 방식

import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input1 = br.readLine().split(" ");
        int n = Integer.parseInt(input1[0]);
        int k = Integer.parseInt(input1[1]);
        int b = Integer.parseInt(input1[2]);
        boolean[] signal = new boolean[n+1];
        Arrays.fill(signal, true);
        for(int i=0 ; i<b; i++){
            signal[Integer.parseInt(br.readLine())] = false;
        }
        
        
        
        int count=0;
        for(int left =1;left<k+1;left++){
            count+= signal[left]? 1:0;
            
        }
        int max = count;
        for(int left =2; left<n-k+2; left++){
            if(signal[left-1]) count--;
            if(signal[left-1+k]) count++;
            max = Math.max(max,count);
        }
        
        
        System.out.println(k-max);
	}
}