슬라이딩 윈도우란 투포인터 알고리즘의 일종으로 볼 수 있다.
배열의 구간을 훑지만 일정 구간씩 보는 것이다.
0000000000000000 배열이 있을 때
XXX0000000000000
0XXX000000000000
00XXX00000000000
000XXX0000000000
위와 같은 방식으로 일정 구간씩 훌는 것이다.
갯수 세기에 주로 쓰인다.
https://www.acmicpc.net/problem/14465
슬라이딩 윈도우 방식
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);
}
}
'Problem Solving > 투포인터' 카테고리의 다른 글
BOJ13422 도둑 (2) | 2024.03.05 |
---|---|
BOJ10025 게으른 백곰 (0) | 2024.03.05 |
BOJ14465 소가 길을 건너간 이유 5 (0) | 2024.03.05 |
BOJ16472 고냥이 (0) | 2024.03.04 |
BOJ15831 준표의 조약돌 (1) | 2024.03.04 |