[JS] 프로그래머스 / Summer/Winter Coding(~2018) / 기지국 설치

문제

프로그래머스

핵심 아이디어

• 배열을 사용하지 않고 구간만 계산: 모든 아파트에 대해 배열을 만들지 않고, 기지국이 설치된 범위와 그 사이의 전파가 닿지 않는 구간을 계산한다.
• 전파가 닿지 않는 구간을 기준으로 최소 기지국 계산: 기지국이 닿지 않는 구간의 길이를 기준으로 필요한 기지국 개수를 계산하여 효율성을 높인다.
• 기지국 사이의 전파가 닿지 않는 구간 처리: 각 기지국 사이와 마지막 기지국 이후에 전파가 도달하지 않는 구간에 대해 필요한 기지국을 계산한다.

정답

function solution(n, stations, w) {
  const boundary = w * 2 + 1;
  let current = 1;
  let answer = 0;

  stations.forEach(station => {
    let stationStart = station - w;

    if (current < stationStart) {
      let uncoveredLength = stationStart - current;
      answer += Math.ceil(uncoveredLength / boundary);
    }

    current = station + w + 1;
  });

  if (current <= n) {
    let uncoveredLength = n - current + 1;
    answer += Math.ceil(uncoveredLength / boundary);
  }

  return answer;
}