🔎 기지국 설치

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/12979

📄 제출 코드

function solution(n, stations, w) {
    var answer = 0;
    let index = 1;
    let range = 2 * w + 1;

    stations.forEach((el) => {
        if (el - w > index) {
            answer += Math.ceil((el - w - index) / range);
        }
        index = el+ w + 1;
    })
    return answer + Math.ceil((n-index+1)/range);
}

let n = 16;
let stations = [9];
let w = 2;
console.log(solution(n, stations, w));

처음에는 n만큼의 배열을 0으로 다채운 후 station과 전파가 닿는 부분을 1로 세팅하고, 배열의 처음부터 끝까지 돌면서 1을 만날 때 마다 Math.ceil(0갯수 /range)을 하려 하였다.
그러나 정답은 전부 맞았지만, 효율성에서는 모두 시간초과가 발생.
줄이려는 방법을 고민하다가 결국 다른 사람의 코드를 참고하였다.

길이를 가지고 답을 찾아간다.
우선 범위는 2w+1, index는 시작점이다.
stations를 돌면서 전파 범위가 닿는 위치의 시작점은 stations[0] - w다.
범위를 셀때도 2w+1한 이유도 가운데 기지국(1) + 좌우 범위(w)이기 때문!
그래서 stations에 저장된 값이 기지국이니까 기지국에서 -w 하면 시작점이다.

전파의 시작점이 index보다 크다면,
Math.ceil(index에서 부터 전파가 시작하는 부분까지의 거리 / range)를 해준다.
그 후 이제 처음기지국으로부터 왼쪽부분을 계산했으니 그 뒤부분을 세기 위해 index를 첫번째 기지국 범위 다음 부분으로 이동시킨다.
index = el + w +1

기지국 수만큼 반복하기 때문에 마지막 기지국 범위에서 끝지점까지를 계산해서 결과를 return한다.

🎲 이전 코드

function solution(n, stations, w) {
    let arr = Array(n).fill(0);
    var answer = 0;
    let len = w * 2 + 1;

    for (let i = 0; i < stations.length; i++) {
        let idx = stations[i] - 1;
        arr[idx] = 1;
        for (let j = 0; j < w; j++) {
            if (idx + 1 > n) break;
            idx += 1;
            arr[idx] = 1;
        }
        idx = stations[i] - 1;
        for (let k = 0; k < w; k++) {
            if (idx - 1 < 0) break;
            idx -= 1;
            arr[idx] = 1;
        }
    }
    console.log(arr)

    let chk = 0;
    let save = [];
    for (let i = 0; i < n; i++) {
        if (arr[i] == 0) chk++;
        else {
            save.push(chk);
            chk = 0;
        }
        if (i == n - 1 && chk != 0) {
            save.push(chk);
        }
    }

    save.forEach(el => {
        answer += Math.ceil(el / len);

    })
    console.log(save);
    return answer;
}

let n = 16;
let stations = [9];
let w = 2;
console.log(solution(n, stations, w));

📘 참고

https://after-newmoon.tistory.com/94