https://school.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 rangeS = 1;
        for (int i=0; i<stations.length; i++) {
            int rangeE = stations[i] - w;
            for (int j=rangeS; j<rangeE; ) { // i번 기지국의 앞쪽 중 아직 배치되지 않은 구역을 탐색
                answer++;
                j+=(2*w + 1);
            }
            rangeS = stations[i] + w + 1;
        }
        
        // 마지막 기지국을 기준으로 아직 배치되지 않은 뒤쪽을 탐색
        for (int j=rangeS; j<=n; ) {
            answer++;
            j+=(2*w + 1);
        }
        
        return answer;
    }
}

개선 풀이

위 로직에서 for문 돌던 로직을 수학적으로 몫과 나머지를 사용해서 구현하도록 개선했다.

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        int rangeS = 1;
        int rangeE;
        for (int i=0; i<stations.length; i++) {
            rangeE = stations[i] - w;
            if (rangeS < rangeE) {
                answer += ((rangeE - rangeS)/(2*w+1));
                if ((rangeE - rangeS)%(2*w+1) != 0) answer++;
            }
            rangeS = stations[i] + w + 1;
        }
        
        rangeE = n + 1;
        if (rangeS < rangeE) {
            answer += ((rangeE - rangeS)/(2*w+1));
            if ((rangeE - rangeS)%(2*w+1) != 0) answer++;
        }
        
        return answer;
    }
}

효율성 테스트에서 시간이 꽤나 많이 개선된 모습을 확인 가능하다.