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

📌 Problem

일렬로 이루어진 아파트들의 옥상에 기지국을 설치하려고 한다. 기지국은 w 만큼의 전파력을 가지고 있는데 설치한 곳으로 부터 +w, -w인 아파트까지 전파가 도달하는 것이다. 예를 들어 5번 아파트에 2의 전파력을 가진 기지국을 설치하면 3 ~ 7까지의 아파트에 전파가 도달한다. 아파트는 1번부터 n번까지로 이루어져 있다. 아파트의 수 n과 전파력 w 그리고 현재 기지국이 설치되어 있는 아파트 번호 배열이 주어진다고 하였을 때 최소한의 기지국을 추가 설치하여 아파트 전체에 전파가 도달하도록 하려고한다. 설치해야하는 최소한의 기지국 수를 구하여라.

📌 Solution

전파가 도달하지 않은 구간이 M만큼 있다고 가정해보자. 전파력이 W일 때 여기에 설치해야 하는 기지국의 수는 우선 $\frac{M}{2W + 1}$ 이다. 예를 들어 길이가 10인 미전파 구역을 W = 2인 기지국으로 채우기 위해서는 최소 2개가 필요하다. 하지만 나누어 떨어지지 않는 경우에는 1개를 추가로 설치해야 한다. 위의 경우에서 길이가 11이라면 3개의 기지국을 설치해야하는 것이다.

주어진 stations를 탐색하면서 기지국의 전파가 도달하지 않는 구역의 길이를 구하고 이를 위의 방식으로 계산하여 최소한으로 설치해야하는 기지국의 숫자를 구할 수 있다.

📌 Code

class Solution {
    public int solution(int n, int[] stations, int w) {
        int count = 0, from = 1, to;    
        for (int station : stations) {
            to = station - w - 1;
            if (from <= to) count += requiredNumber(to - from + 1, w);
            from = station + w + 1;
        }
        if (from <= n) count += requiredNumber(n - from + 1, w);
        return count;
    }

    private int requiredNumber(int length, int w) {
        return (length / (2 * w + 1)) + (length % (2 * w + 1) > 0 ? 1 : 0);
    }
}