[JS] 기지국 설치

그리디를 활용하여 해결하였다!

 

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

프로그래머스

 

먼저 stations 배열을 정렬을 해준다.

이후 기지국을 넣어줘야하는 구간을 구해준 후 해당 구간에 설치해야 하는 기지국 수를 더해주면서 구해줬다.

 

여기까진 크게 어렵지 않은데 신경써야할 부분이 2가지 정도가 있다.

 

1. 구간이 음수로 나오는 경우 기지국 설치가 필요없는 경우이므로 패스해준다.

2. 마지막 기지국부터 마지막 아파트까지의 부분을 생각해줘야 한다.

 

 

 

 

 

 

function solution(n, stations, w) {
    
    stations.sort((a,b) => a-b)
    
    let ret = 0
    let dist = 1
    const range = 2*w+1 //기지국 범위
    
    for (const station of stations){
        const tmp = station - w - dist //미설치된 구간
        if (tmp > 0) ret += ~~(tmp / range) + (tmp%range ? 1 : 0) //기지국 설치
        dist = station + w + 1 //다음 미설치된 시작점
    }
    //마지막 기지국 이후 설치
    if(dist <= n) ret += ~~((n+1-dist) / range) + ((n+1-dist)%range ? 1 : 0)
    
    
    return ret
    
}