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

문제 링크

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

문제 내용

다음과 같이 기지국이 설치되어 있다. 기지국은 설치한 위치 기준 양방향으로 w길이로 전파를 전달하는데 기지국을 최소로 추가하면서 모든 건물에 전파를 전달하려고 한다.

문제 풀이

전파하지 못하는 구간을 첫 기지국의 왼쪽, 기지국들의 사이, 마지막 기지국의 오른쪽으로 나누어서 계산을 진행하였다.

기지국이 양방향으로 전파를 전달하기 때문에 기지국 하나가 전파할 수 있는 거리를 2xw + 1(기지국 건설 위치)로 놓고 전달되지 못하는 구간을 파악해 기지국 하나가 전파할 수 있는 거리로 나눈 몫을 통해 필요 기지국 개수를 구하였다.

나머지가 있어 나누어 떨어지지 않는 경우 기지국 1개가 추가로 설치한 경우로 판단한 뒤 개수를 계산한다.

코드

import java.lang.Math;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int stationSize = stations.length-1;
        
        // 첫 번째 기지국이 해당 기지국의 왼쪽을 모두 전파하지 못하는 경우
        if(1 < stations[0] - w){
        	// 전파하지 못하는 구간의 길이를 기지국 하나가 전파할 수 있는 거리로 나눈 몫을 더해준다.
            answer += Math.floorDiv(Math.max(0, stations[0]-w-1), w*2+1);
            // 나머지가 있는 경우 기지국 1개 추가 
            if(Math.floorMod(Math.max(0, stations[0]-w-1), w*2+1) != 0){
                answer += 1;
            }
        }
        
        // 각 기지국들의 사이에 전파하지 못하는 구간이 있는 경우 
        for(int i=0; i<stationSize; i++){
        // 같은 방식으로 추가 건설
            answer += Math.floorDiv(Math.max(0, stations[i+1]-2*w-stations[i]-1), w*2+1);
            if(Math.floorMod(Math.max(0, stations[i+1]-2*w-stations[i]-1), w*2+1)!=0) {
                answer += 1;
            }
        }
        
        // 마지막 기지국이 오른쪽을 모두 전파하지 못하는 경우
        if(stations[stationSize] + w < n ) {
        // 같은 방식으로 추가 건설
            answer += Math.floorDiv(Math.max(0, n - stations[stationSize] - w), w*2+1);
            if(Math.floorMod(Math.max(0, n - stations[stationSize] - w), w*2+1) != 0){
                answer += 1;
            }
        }

        return answer;
    }
}