(javascript) 프로그래머스 기지국 설치

[문제링크]

https://programmers.co.kr/learn/courses/30/lessons/12979?language=javascript

[문제]

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

[풀이]

문제를 읽었을 때, 제일 먼저 떠오른 풀이는 1~N까지 포함 할 수 있는 배열을 만들어 하나하나 증가시키며 시뮬레이션을 돌리려 하였습니다. 하지만 메모리 측면에서, 성능측면에서 상당히 부담스러울 것으로 생각이 들었습니다.( N의 최대값이 200,000,000 ...)

따라서 배열은 선언하지않고, 시뮬레이션 돌리기 위한 $i$(아파트 번호)값과 station만으로 코드를 짰습니다. 어려운 계산은 아니나, 코딩에서 숫자의 계산은 1값하나로 오차가 많이 나기때문에 수식을 짜는데에 시간을 많이 쏟았습니다.
코드의 전체적인 구조는 반복문을 통해 현재 $i$값을 갱신시켰습니다. 이에는 2가지 규칙이 존재합니다.
1. $i$값 위치에 있는 아파트가 stations의 영향을 받으면 station이 끝나는 부분까지 i값을 증가시키켰습니다.
2. $i$값 위치에 있는 아파트가 전파를 받지 않는 다면 놓을 수 있는 최대 거리를 가진 위치에 기지국을 설치하고 그 영향을 받지 않는 번호로 i값을 갱신합니다. (새로 기지국을 설치했기 때문에 answer++)

이 두가지의 규칙만으로 진행하였고, 별도의 에러처리를 해주었습니다.
효율성체크 1,4번에서 에러가 생긴 원인은 stations가 empty array로 주어졌을때, 발생하였습니다. 따라서 변수를 선언할때, empty stations 일 경우, station의 초기값을 N보다 크게 선언하여 영향을 받지 않도록 하였습니다.

[성공코드]

function solution(n, stations, w) {
  var answer = 0;
  var station

  if (stations.length == 0) {
    station = n + w + 1
  }
  station = stations.shift()

  var i = 1
  while (i <= n) {
    // i가 전파를 못받는 지점일때, 설치하기
    if (station - w > i) {
      // 연속된 비 전파구역에 최소한으로 설치하기
      var m = Math.ceil((station - w - i) / (2 * w + 1)) 
      i = station + w + 1
      answer += m
    }

    //station 안에 존재 할 때
    if (station - w <= i) {
      i = station + w + 1
      if (stations.length) {
        station = stations.shift()
      }
      else {
        station = n + w + 1
      }
    }

  }

  return answer;
}