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

문제

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

프로그래머스

 

---

 

문제 개요

N개의 아파트가 일렬로 배치되어 있으며, 일부 아파트 옥상에 4G 기지국이 설치되어 있습니다.
5G 기지국은 4G 기지국보다 전파 도달 범위가 좁기 때문에 모든 아파트에 전파를 전달하려면 기존 5G 기지국만으로는 부족할 수 있습니다.

문제의 목표는 기존 기지국의 위치와 전파 범위를 기반으로, 모든 아파트에 전파를 전달하기 위해 추가로 설치해야 할 5G 기지국의 최소 개수를 구하는 것입니다.

 

접근 방법

1. 전파가 닿지 않는 구간 파악
   • 기지국이 커버하는 범위를 계산하면서 전파가 닿지 않는 구간을 확인합니다.
   • 기지국의 커버 범위: station - W부터 station + W까지.
   • 현재까지 전파가 도달한 마지막 아파트 위치를 current 변수로 관리합니다.
     • current보다 작은 위치는 이미 전파가 도달했으므로 무시합니다.
     • current보다 큰 위치는 새로운 기지국이 필요합니다.
2. 추가 기지국 설치
   • 커버되지 않는 구간의 길이를 계산한 뒤, 하나의 기지국이 커버할 수 있는 범위 (2 * W + 1)로 나눕니다.
   • 나머지가 있는 경우, 한 개의 기지국이 더 필요하므로 올림 처리합니다.
3. 기존 기지국 이후 처리
   • 마지막 기지국 이후에도 전파가 닿지 않는 구간이 남아 있다면, 이 구간에 대해 추가 기지국 설치를 계산합니다.

 

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int current = 1; // 현재 아파트 위치
        int range = 2 * w + 1; // 한 기지국이 커버할 수 있는 범위

        for (int station : stations) {
            // 기존 기지국이 커버하지 못하는 왼쪽 구간 계산
            if (current < station - w) {
                int leftCoverage = station - w - current;
                answer += Math.ceil((double) leftCoverage / range);
            }
            // 커버 가능한 범위의 다음 위치로 이동
            current = station + w + 1;
        }

        // 마지막 기지국 이후 커버하지 못한 구간 처리
        if (current <= n) {
            int remaining = n - current + 1;
            answer += Math.ceil((double) remaining / range);
        }

        return answer;
    }
}