기지국 설치

문제 정보

• 프로그래머스 Lv.3
• 문제 링크

풀이

기지국을 최소로 세우려면, 전파 범위의 중복을 최소화해야 한다.

문제에서 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다 라고 했으므로 기지국 하나의 전파 도달 거리는 2w + 1이다.

그러므로 설치하는 기지국의 개수는 다음과 같다. (여기서 $r$은 전파가 닿지 않는 아파트의 개수)

$$\begin{array}{rl}& \{\begin{array}{l}\frac{r}{2w+1}\cdots \text{if }r\mathrm{mod}(2w+1)=0\\ \lfloor \frac{r}{2w+1}\rfloor +1\cdots \text{if }r\mathrm{mod}(2w+1)\ne 0\end{array}\\ & \\ & \therefore \text{설치하는 기지국의 개수}=\lceil \frac{2w+1}{r}\rceil \end{array}$$

전파가 닿지 않는 아파트의 개수는 전파가 닿지 않는 아파트의 끝 번호 - 전파가 닿지 않는 아파트의 시작 번호 + 1로 구할 수 있다.

여기서 전파가 닿지 않는 아파트의 끝 번호는 station(기지국이 설치된 아파트 번호) - w(전파 범위) - 1로 계산한다.

한 구간에 설치해야 하는 기지국의 개수를 구한 후엔 station + w + 1로 전파가 닿지 않는 아파트의 시작 번호를 갱신해준다.

또한 stations를 모두 순회한 후, 마지막으로 전파가 닿지 않는 아파트의 번호가 $n$보다 작거나 같은지 검사해야 한다.

$n$보다 작다면 전파가 닿지 않는 아파트가 있다는 것이고, $n$과 같다면, 마지막 아파트에 전파가 닿지 않는다는 것이므로 추가로 설치해야 한다.

코드

import java.util.*;
 
class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
 
        int start = 1;
        for (int station : stations) {
            int end = station - w - 1;
           
            answer += getStationCnt(start, end, w);
            
            start = station + w + 1;
        }
        
        if (start <= n) 
            answer += getStationCnt(start, n, w);
 
        return answer;
    }
    
    private int getStationCnt(int start, int end, int w) {
        int range = end - start + 1;
        
        if (range <= 0)
            return 0;
        
        return (int) Math.ceil((double) range / (2 * w + 1));
        
    }
}