[알고리즘] 프로그래머스 - 기지국 설치

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

문제설명
아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

제한사항

• N: 200,000,000 이하의 자연수
• stations의 크기: 10,000 이하의 자연수
• stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
• W: 10,000 이하의 자연수

이 문제를 2가지 방법으로 접근해 봤었는데
1. 0번인덱스 부터 시작해 모든 인덱스에 접근해서 기지국 범위내에 들어가는지 확인했었음, 안들어가면 또 어디에 기지국을 설치해야 하는지 찾음
2. 다른방법은 초기 설치된 기지국범위를 제외한 나머지 영역을 구해 그 영역을 (2*w+1)로 나눠서 올림값을 구했다. 이 방법도 모든 인덱스를 확인하는 작업을 하는데

이 두 방법 모두 정확도는 통과했지만 효율성에서 시간초과가 났다. 모든 인덱스를 확인하는 방법이 효율적이지 않다는 의미이기때문에 모든 아파트를 확인하는 방법말고 index를 사용해서 접근하는 방식이 더 효율적일것같다.

function solution(n, stations, w) {
    let answer = 0; // 추가로 설치할 기지국의 개수를 찾음
    let startIndex = 0; // 기지국설치를 시작할 index
  
    // stations의 길이만큼 for문을 돌리는 이유
    // for문을 한번 돌면 해당하는 stations의 값의 왼쪽범위에서 필요한 기지국수를 구함
    for(let i = 0 ; i < stations.length ; i++){
        let leftIndex = stations[i] - w - 1; // 기지국설치해서 영향을 받는 index 중 가장 왼쪽값
       // (2 * w) +1 은 하나의 기지국이 도달할수 있는 아파트 개수
        answer += Math.ceil((leftIndex - startIndex) / ((2 * w) + 1));
        startIndex = stations[i] + w; 
    }
  
    // stations의 마지막값이 도달하지 못하는 오른쪽 범위에서 설치해야할 기지국 개수를 구함
    answer += Math.ceil((n - startIndex) / ((2 * w) + 1));  
    return answer;
}