기지국 설치

Solution

N이 최대 2억개이므로 배열에 상태를 저장하면서 계산하는 것은 불가능하다고 생각하였고, 범위 안의 아파트의 개수에 대한 기지국의 개수를 한번에 구할 수 있는 방법이 있다고 판단하였다.

1. stations 배열은 오름차순으로 정렬되어 있으므로, 별도의 index를 정의해서 처음부터 배열에 나온 범위전까지의 아파트 개수를 구한다.
2. 기지국 하나당 2 * w + 1 개의 범위를 가지므로,
   아파트의 개수 / 기지국의 범위 + 1(나머지가 있을 경우) 를 계산하면 기지국의 최솟값이 나온다.

Code

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        
        int answer = 0;
        int idx = 1; // 시작 인덱스
        int area = 2 * w + 1; // 기지국 범위
        
        for(int station : stations){
        	// 해당 기지국의 최소 최대범위
            int min = station - w >= 1 ? station - w : 1; 
            int max = station + w <= n ? station + w : n;
            
            // 인덱스가 최소값보다 작다는 것은 기지국 영향을 안받는 아파트가 있다는 뜻
            if(idx < min){
                int count = min - idx;
                answer += count % area == 0 ? count / area : count / area + 1;
            }
            
            idx = max + 1;
        }
       
       // 마지막 범위 처리
        if(idx < n + 1){
            int count = n + 1 - idx;
            answer += count % area == 0 ? count / area : count / area + 1;
        }
        
        return answer;
    }
}