문제

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

현재 4g 기지국이 설치되어있다.
이걸 5g 기지국으로 변경하면 전체 아파트에 전파의 범위가 도달하지 못할수도 있다.
5g기지국을 최소로 설치하면서 전체 아파트에 전파를 도달하려면 기지국을 몇개 설치해야하는가?

• n: 11
• stations: [4, 11]
• w: 1

아래 예시는 위의 입력이 있을경우를 설명한다.

• 4, 11에만 기지국을 설치한 경우
  
• 4, 11에 더해 최소로 기지국을 설치한 경우
  

문제 접근

처음에는 n개의 배열을 만들어서 station의 범위만 1을 초기화 하고 나머지는 0으로 초기화후
아래 두가지 경우에 result를 1 늘렸다

1. 배열을 전체탐색하며 기지국 범위만큼 cnt가 추가되면 result를 1 늘린다.
2. 배열을 전체탐색하며 이전까지 0이었는데 1을 만나면 result를 1 늘린다.

그렇게 짠 기존 방식은 아래와 같다.

const solution = (n, stations, w) => {
  const apts = Array(n + 1).fill(0);
  const range = w * 2 + 1;
  let cnt = 0;
  let rst = 0;
  let now = 0;

  stations.forEach(station => {
    for (let i = station - w; i <= station + w; i++) {
      apts[i] = 1;
    }
  });

  for (let i = 1; i <= n; i++) {
    const apt = apts[i];
    if (apt === 0) {
      now = 0;
      cnt++;
      if (cnt === range) {
        cnt = 0;
        rst++;
      }
    }
    if (apt === 1 && now === 0) {
      if (cnt > 0) rst++;
      now = 1;
      cnt = 0;
    }
  }
  if (cnt > 0) rst++;
  return rst;
};

하지만 이 방법에는 치명적인 단점이 존재한다.
n의 범위가 최대 2억개라서 무조건 시간초과가 난다는거다.
그래서 다른 방법을 찾아야 하는데 생각하는 방식을 조금 바꿔봤다.

원래 n을 끝까지 돌면서 기존 기지국에 더해서 새로운 기지국을 박는 방식으로 생각을 했는데
그냥 station만 돌면서 기존 범위를 갱신해주며 기지국이 닿지 않는 범위만 기지국을 더해주는 방식으로 바꿔줬다.

예를들어 아래처럼 맨 위의 예제가 입력으로 주어지면

• n: 11
• stations: [4, 11]
• w: 1

0. 처음에 마지막 범위 = 1로 초기화환다.
1. 처음 station은 4인데 이 기지국의 범위는 w가 1이므로 3~5다. 이 기지국 앞에 전파가 닿지 않는 범위는 1 ~ 2, 2인데 이 범위는 기지국 한개로 커버가 가능하므로 result를 1 추가한다.
2. 두번째 station은 11이다. 커버 범위는 10~11이다. 이 기지국 앞에 전파가 닿지 않는 범위는 6~9, 4이다. 이 범위는 기지국 두개로 커버가 가능하므로 result에 2를 추가한다.
3. 만약에 끝에 커버되지 않는 범위가 있을경우 위의 방식과 동일하게 기지국의 개수를 구해 더해주면 되는데 현재 11까지 모두 커버되므로 추가되는 기지국은 없다.

이를 코드로 표현하면 아래와 같다.

정답코드

const solution = (n, stations, w) => {
  const range = w * 2 + 1;
  let result = 0;
  let lastCoverage = 1;

  stations.forEach(now => {
    const right = now - w - 1;
    const coverRange = right - lastCoverage + 1;
    const needStationNum = Math.ceil(coverRange / range);

    result += needStationNum;
    lastCoverage = now + w + 1;
  });
  // if문이 없어도 결국 남은 범위가 없으면 0이 추가돼서
  // if문은 없어도 무방하긴 하다.
  if (lastCoverage <= n) {
    const coverRange = n - lastCoverage + 1;
    const needStationNum = Math.ceil(coverRange / range);
    result += needStationNum;
  }

  return result;
};