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

코드 힌트

1. 문제 핵심:
   • 기지국은 특정 범위를 커버하며, 기지국이 커버하지 않는 빈 구역에 추가 기지국을 설치해야 합니다.
   • 새로운 기지국을 설치할 때는, 각 기지국이 커버할 수 있는 범위를 최대한 활용하여 최소 개수로 설치해야 합니다.
2. 기지국 범위 계산:
   • 기지국이 커버할 수 있는 범위는 좌우로 w만큼이고, 따라서 한 기지국이 커버하는 전체 범위는 2 * w + 1입니다.
3. 구역 처리 순서:
   • 각 기지국이 커버하지 않는 구역을 찾아 추가 기지국을 배치합니다.
   • 각 기지국이 커버하는 구역은 계산하여 확인된 위치를 그 구역의 오른쪽 끝으로 이동합니다.
4. 마지막 구역 처리:
   • 모든 기지국이 커버한 이후에도 남은 구역이 있을 경우, 그 구역에 추가 기지국을 설치합니다.

 

---

정답은 더보기 클릭

class Solution {
    public int solution(int n, int[] stations, int w) {
        int result = 0; // 추가로 설치해야 할 기지국의 수를 저장하는 변수
        
        int pos = 1; // 현재 확인 중인 위치, 아파트 단지의 시작 위치는 1
        int range = 2 * w + 1; // 한 기지국이 커버하는 범위 (좌우 w칸씩 + 1칸)
        
        for (int station : stations) {
            int l = station - w; // 현재 기지국이 커버하는 왼쪽 끝
            int r = station + w; // 현재 기지국이 커버하는 오른쪽 끝
            
            // 기지국의 범위를 아파트 단지 범위에 맞게 조정
            if (l < 0) l = 0;
            if (r > n) r = n;
            
            // 현재 기지국이 커버하지 않는 구역에 추가 기지국 설치
            if (pos < l) {
                // 커버되지 않는 구역의 크기만큼 필요한 기지국 수를 계산
                result += (l - pos) % range == 0 ? (l - pos) / range : (l - pos) / range + 1;
            }
            
            // 현재 위치를 기지국이 커버하는 오른쪽 끝으로 이동
            pos = r + 1;
        }
        
        // 마지막 기지국 이후 남은 구역에 추가 기지국 설치
        if (pos <= n) {
            result += (n - pos + 1) % range == 0 ? (n - pos + 1) / range : (n - pos + 1) / range + 1;
        }
        
        return result; // 총 추가된 기지국의 수 반환
    }
}