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

1. 문제 풀이 아이디어

• 주어진 기지국(stations)과 전파 범위(w)를 이용해 커버되지 않는 영역을 계산하고, 추가로 필요한 기지국의 수를 구해 문제를 해결한다.

2. 나의 정답 코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int prev = -w;
        int dif;
        for (int i : stations) {
            dif = i - prev - w * 2 - 1;
            prev = i;
            answer += (dif + w * 2) / (w * 2 + 1);
        }
        dif = n + w - prev - w * 2;
        answer += (dif + w * 2) / (w * 2 + 1);
        return answer;
    }
}

3. 정리

• prev는 계산할 때 기지국을 기준으로 계산되므로 시작값은 w로 설정한다.

• stations를 순회하며 i - prev - w * 2 - 1로 현재 기지국과 이전 기지국 사이의 커버되지 않은 범위를 구한다.

• 계산한 범위는 w * 2 + 1로 나눈 후 올림 처리하여 answer에 더한다.

• 반복문을 종료한 후, 마지막 기지국 이후의 구간을 계산하기 위해 마지막 기지국의 위치를 n + w + 1로 설정하고, 그 구간의 커버되지 않은 범위를 계산하여 필요한 기지국을 구한 뒤 answer에 더한다.

• 최종적으로 answer를 반환하여 문제를 해결한다.