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

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

코딩테스트 연습 - 기지국 설치

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int dist=(2*w)+1;
        int s=1;
        int start=0, end=0;
        for (int i=0; i<stations.length; i++){
            start=stations[i]-w<0?0:stations[i]-w;
            end=stations[i]+w>n?n:stations[i]+w;
            int len=start-s;
            if (len>0){
                if (len%dist==0){
                    answer+=len/dist;
                }
                else{
                    answer+=(len/dist)+1;
                }
            }
            s=end+1;
        }
        if (n>end){
            answer+=((n-end)%dist==0 ? (n-end)/dist : (n-end)/dist+1);
        }
        return answer;
    }
}

그리디 문제.

기지국이 커버하는 범위를 구해준 뒤, 그 범위 사이사이의 길이에 대해 커버할 수 있는 집의 수로 나눠준다.

나머지가 0으로 떨어지면=> 그 몫을 취하고, 0으로 떨어지지 않으면 몫+1 해준다.

 

범위 사이사이의 길이는 i번째 기지국이 커버하는 범위의 끝+1 부터, i+1번째 기지국이 커버하는 범위의 시작-1 까지의 길이를 구해주면 된다. 

 

다른 분(https://minnnne.tistory.com/46)의 코드를 보니,

기지국이 겹쳐있을 경우 start 지점을 끝+1로 놓는다.