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

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

프로그래머스

접근 방법

1. 기지국이 필요한 구간의 길이 = d 라고할때, 이 구간에 필요한 기지국의 개수는
   1. d % w == 0 이면 d / w 개가 필요하다
   2. 아니면 d / w + 1개가 필요하다
2. 그렇다면 슬라이딩 윈도우로 필요한 구간을 찾고 "ans += fnc(구간)" 형태로 값을 더해주면 되겠다 !  => 시간 초과 발생
3. 사실 구간은 solution 함수의 파라미터 만으로 알 수 있다
   1. 0 ~ stations[0]-w-1 , stations[0]+w+1 ~ stations[2]-w-1, ... , stations[stations.length-1]+w+1 ~ n

 

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int ans = 0;
        
        ans += getWidth(1, stations[0] - w - 1, 2*w+1);
        for(int i = 1; i < stations.length ; i++){
            ans += getWidth(stations[i-1]+w+1, stations[i]-w-1, 2*w+1);
        }
        ans += getWidth(stations[stations.length-1]+w+1, n, 2*w+1);
        
        return ans;
    }
    int getWidth(int l,int r,int w){
        int num = r - l + 1;
        if(num <= 0) return 0;
        if(num % w  == 0) return num / w;
        return num / w + 1;
    }
}