슬라이딩 윈도우 (SV2 소가 길을 건너간 이유 5)

문제

14465 소가 길을 건너간 이유 5 (SV2)
https://www.acmicpc.net/problem/14465

알고리즘 분류: 슬라이딩 윈도우, 누적합

풀이

입력값

10 6 5
2
10
1
5
9

입력값 N의 길이의 배열 하나를 생성하여 배열을 고장난 신호등은 0을 정상인 신호등은 1로 한다.

[ 0, 0, 1, 1, 0, 1, 1, 1, 0, 0 ]

여기서 슬라이딩 윈도우 알고리즘을 사용한다.
검사할 윈도우의 크기는 입력값 K 이며 각 윈도우의 내부 요소의 합과 K의 차를 구해 최솟값을 구한다.

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const [input, ...inputArr] = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const [N, K, B] = input.split(" ").map(Number);
const repaired = inputArr.map(Number);

const array = new Array(N).fill(1);
for (const element of repaired) {
  array[element - 1] = 0;
}

let window = array.slice(0, K).reduce((ac, cv) => ac + cv, 0);
let answer = K - window;
for (let i = K; i < N; i++) {
  window += array[i] - array[i - K];
  if (K - window < answer) answer = K - window;
}

console.log(answer);

Today I Learned

슬라이딩 윈도우 기법이란?

• 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다.

위 예시의 윈도우 내의 요소들의 합을 차례로 구한다면 다음과 같다.

• 첫번째 윈도우 요소의 합: 1 + 15 + 1 + 2
• 두번째 윈도우 요소의 합: 1 - (1) + 15 + 1 + 2 + (+6)

이 때, 다음 윈도우의 요소의 합을 구할 때 다음 윈도우의 시작과 끝 인덱스의 요소를 하나씩 합하는 게 아니라
이전의 윈도우에서 첫번째 윈도우 요소를 빼고 끝 인덱스의 다음 인덱스의 요소를 더하면 된다.