[lv3] 기지국 설치

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

 

문제의 핵심은, 기지국 간의 전파 범위는 모두 같다는 것을 시작으로 접근하는 것이다.

 

이 때문에,

A의 왼쪽에 B를 놓았을 때 B의 범위가 A의 오른쪽 범위를 넘는 경우는 없다.

(전파 범위가 모두 다르다면, B를 놓은 곳이 다음 탐색이나 양쪽 끝단에까지 영향을 미칠 수 있다.)

 

따라서, 추가 기지국을 설치할 때 기존의 기지국과 겹치지 않는 곳 부터 차례대로 설치하면 된다. => 그리디

 

 

해결 방법

 

1. 가장 왼쪽의 기지국의 왼쪽 전파 범위에서 시작, 왼쪽 끝의 아파트에 닿을 때 까지 추가 기지국을 세운다.

 

2. 가장 오른쪽의 기지국의 오른쪽 전파 범위에서 시작, 오른쪽 끝의 아파트에 닿을 때 까지 추가 기지국을 세운다.

 

3. 기지국간의 비교

for 0 to stations.length - 2

i번째 기지국의 오른쪽 전파 범위 부터, i+1번째 기지국의 왼쪽 전파 범위에 닿을 때 까지 채운다.

 

(i번째 기지국을 기준으로 하던, i+1번째 기지국을 기준으로 하던 범위만 최대한 겹치지 않게 놓는다면 필요한 추가 기지국 개수는 바뀌지 않는다.)

 

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;

        // +1은 기지국을 설치한 아파트에 해당
        int sScope = w * 2 + 1;

        int first = 0;
        int firstAt = stations[first];
        int firstST = firstAt - w;
        int firstED = firstAt + w;

        int last = stations.length -1;
        int lastAt = stations[last];
        int lastST = lastAt - w;
        int lastED = lastAt + w;

        // 전파가 통하는 제일 끝단의 아파트 위치
        int left = firstST;
        int right = lastED;

        // 최소 1번째 아파트 까지는 전파가 닿아야 함
        while(left > 1) {
            left -= sScope;
            answer++;
        }

        // 최소 n번째 아파트 까지는 전파가 닿아야 함
        while(right < n) {
            right += sScope;
            answer++;
        }

        // 지기국간의 전파 범위 비교
        for(int i=0; i<stations.length -1; i++) {

            int at = stations[i];
            int st = at - w;
            int ed = at + w;

            int next = stations[i+1];
            int nST = next - w;
            // int nED = next + w;

            // i번째 기지국의 ed부터 i+1번째 기지국의 st까지 닿게 설치
            // i+1번째 기지국의 st가 7이라면, 최소 6까지 닿아야 함
            while(ed < nST - 1) {
                ed += sScope;
                answer++;
            }
        }

        return answer;
    }
}