[JavaScript] 프로그래머스 - 기지국 설치

[문제]

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

프로그래머스

 

[풀이]

전파력이w인 경우, 최대 2*w + 1 거리만큼 아파트들에게 전파가 도달됩니다.

따라서 전파가 도달하지 않은 연속된 아파트에 최소의 기지국으로 전파를 전달하는 방법은 다음과 같습니다.

• Math.ceil(연속된 아파트 길이/(2*w+1))

예시 1번과 같이 w=1인 경우 전파가 도달하지 않은 연속된 아파트의 길이는 다음과 같습니다.

 

 

따라서 Math.ceil(2/3) +  Math.ceil(4/3) = 1 + 2 = 3이 정답이 됩니다.

 

 

이를 코드로 구현하기 위해 현재 기준점 idx = 1로 초기화한 후, stations를 탐색하며 아파트의 길이를 구합니다.

• start = 3, end = 5 이므로 길이는 start - idx = 2이며, idx = end + 1 = 6으로 갱신
• start = 10, end = 11이므로 길이는 start - idx = 4이며, idx = end + 1 = 12으로 갱신

따라서 전파가 없는 아파트의 길이는 2와 4인것을 구할 수 있습니다.

 

[코드]

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

    let idx = 1;
    stations.forEach((station) => {
        let [start, end] = [station - w, station + w];
        if(idx > n) {
            return answer;
        }
        if(start > idx) {
            answer += Math.ceil((start - idx)/(2*w+1));
        }
        idx = end+1;
    })
    if(idx <= n) {
        answer += Math.ceil((n - idx + 1)/(2*w+1));
    }
    return answer;
}