기지국 설치

문제

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 일부 아파트 옥상에는 4G 기지국이 설치되어 있습니다. 기지국이 설치된 아파트를 기준으로 전파를 양방향으로 W만큼 전달할 수 있습니다. 모든 아파트에 전파를 전달하기 위해 5G 기지국을 추가로 설치하려고 할 때, 추가로 설치해야 하는 기지국 개수의 최솟값을 구하는 프로그램을 작성하는 문제입니다.

• 입력: 아파트의 개수 n (1 ≤ n ≤ 200,000,000), 현재 기지국이 설치된 아파트 번호 배열 stations (크기 10,000 이하), 전파 도달 거리 w (1 ≤ w ≤ 10,000)
• 출력: 추가로 설치해야 하는 기지국의 최소 개수

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

풀이: 전파가 닿지 않는 구간(Gap) 계산 및 탐욕법 적용

기존 기지국이 커버하지 못하는 빈 구간(Gap)의 길이를 구한 뒤, 해당 구간을 모두 덮기 위해 필요한 최소 기지국 개수를 더해가는 효율적인 탐욕법(Greedy) 풀이입니다. N의 크기가 2억이므로 아파트를 하나씩 탐색하면 시간 초과가 발생하며, 주어진 기지국(stations)을 기준으로 건너뛰며 탐색해야 합니다.

• 빈 구간 길이 계산: tmp는 '전파가 닿지 않는 첫 번째 아파트 위치'를 의미하며 1로 시작합니다. 기지국 배열을 순회하며, 기지국의 전파가 닿는 왼쪽 끝(s - w)이 tmp보다 크다면 그 사이 구간(s - w - tmp)은 전파가 닿지 않는 빈 구간입니다.
• 필요한 기지국 수 (올림 나눗셈): 한 기지국이 커버할 수 있는 최대 범위는 2 * w + 1입니다. 빈 구간의 길이를 이 범위로 나누어 올림 처리하면 필요한 기지국의 최소 개수가 나옵니다.
  • 자바에서는 (구간 길이 + 커버 범위 - 1) / 커버 범위 공식을 적용하면 깔끔하게 올림 연산을 할 수 있습니다. 코드의 (s - w - tmp + 2 * w) / (2 * w + 1)가 정확히 이 공식에 해당합니다.
• 기지국 범위 통과: 구간을 처리한 후, tmp를 현재 기지국의 오른쪽 끝 다음 아파트인 s + w + 1로 갱신하여 다음 빈 구간을 찾을 준비를 합니다.
• 마지막 남은 구간 처리: 모든 stations 순회가 끝난 후, 마지막 기지국의 오른쪽부터 n번 아파트까지 전파가 닿지 않는 구간이 남아있을 수 있습니다. 동일한 공식으로 마지막 구간을 덮는 데 필요한 기지국 개수를 ans에 더해줍니다.

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int ans = 0;
        int tmp = 1; // 전파가 닿지 않는 탐색 시작점
        
        for (int s : stations) {
            // 기지국의 왼쪽 범위가 tmp보다 커서 커버 안 되는 구간이 존재하는 경우
            if (tmp < s - w) {
                // (구간 길이 + 커버 범위 - 1) / 커버 범위 -> 정수 올림 공식 적용
                ans += (s - w - tmp + 2 * w) / (2 * w + 1);
            } 
            
            // 현재 기지국이 커버하는 오른쪽 끝 다음 칸으로 갱신
            tmp = s + w + 1;
        }
        
        // 마지막 기지국 이후부터 N번 아파트까지 남은 빈 구간 처리
        if (tmp <= n) {
            ans += (n + 1 - tmp + 2 * w) / (2 * w + 1);
        }
        
        return ans;
    }
}

알고리즘 분류

구현 (Implementation), 탐욕법 (Greedy)