[백준] 소가 길을 건너간 이유 5 (JS)

문제

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

농부 존의 농장에 원형 길이 있다고 했지만, 길은 그뿐만이 아니다. 그 옆에 일자형 길이 있는데, 1번부터 N번까지의 번호가 붙은 횡단보도 N (1 ≤ N ≤ 100,000)개로 이루어져 있다. 교통사고를 방지하기 위해 존은 각 횡단보도에 신호등을 설치해 놓았다. 그러던 어느 날, 강력한 뇌우로 인해 몇몇 신호등이 망가졌다. 존은 연속한 K개의 신호등이 존재하도록 신호등을 수리하고 싶다. 이번에도 우리가 존을 도와주자.

입력

첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.

출력

정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다.

풀이

1. 1번부터 N번까지의 신호등 상태를 나타내는 배열을 생성하고, 모든 신호등을 정상 상태인 1로 설정한다.

2. 입력으로 주어진 고장난 신호등 번호들을 순회하며, 해당 위치를 0으로 바꿔 고장 상태를 표시한다.
3. 길이가 K인 첫 번째 구간(윈도우)을 설정하고, 해당 구간 내에 있는 정상 신호등(값이 1인 요소)의 개수를 계산한다.

4. 윈도우를 오른쪽으로 이동하면서, 새롭게 포함되는 신호등과 제외되는 신호등의 상태를 반영하여 정상 신호등의 개수를 갱신한다.

5. 각 구간에서 확인한 정상 신호등의 최대 개수를 기준으로, K - 정상 신호등 수를 계산하여 최소 수리 개수를 구한다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const [N, K, B] = input[0].split(" ").map(Number);
const brokenList = input.slice(1).map(Number);

Solution = (N, K, brokenList) => {
    const road = Array.from({length: N}, (v, i) => 1);
    
    brokenList.forEach(broken => {
        road[broken - 1] = 0;
    })
    
    let windowSum = 0;
    for (let i = 0; i < K; i++) {
        windowSum += road[i];
    }
    
    let workingLights = windowSum;
    for (let i = K; i < N; i++) {
        windowSum = windowSum - road[i - K] + road[i];
        workingLights = Math.max(windowSum, workingLights);
    }
    
    console.log(K - workingLights);
}

Solution(N, K, brokenList);