[프로그래머스] 기지국 설치 Java 풀이 및 해설

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

프로그래머스

풀이 방법

비전파 길이가 N일때

이 비전파 길이를 최소한 기지국으로 전파를 하는 기지국의 개수는

비전파 길이를 기지국 하나가 전파 가능한 길이로 나누면 된다.

 

위의 수학적 방법을 통해

 

반복문으로

첫번째 기지국의 왼쪽 비전파 길이를 채우고

두번째 이상 기지국 i는 i-1번째 기지국의 오른쪽 전파 끝 위치를 계산해서

i 기지국의 왼쪽 전파 끝과 i-1번째 기지국의 오른쪽 전파 끝 위치 사이의 길이를 계산해서

사이에 몇개의 기지국이 필요한지 계산한다.

 

반복문을 다 돌고

마지막 기지국의 오른쪽 비전파 길이를 따로 계산해주었다.

 

전체 코드

import java.util.*;
class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        
        for(int i=0; i<stations.length; i++) {
            
            int len = 0;
            if(i == 0) { // 첫번째 기지국
                len = stations[i]-w-1; // 의 왼쪽 비전파 길이
            } else {
                len = (stations[i]-w-1) - (stations[i-1]+w+1) + 1; // i-1 기지국과 i 기지국 사이의 비전파 길이
            }
            
            if(len > 0) {
                answer += len / ((2*w)+1);
                if(len % ((2*w)+1) != 0) // 나머지가 존재하면 기지국 1개 추가해야함.
                    answer++;
            }
        }
        
        // 마지막 기지국의 오른쪽 방향 전파가 끝까지 도달하지 않는다면
        if(stations[stations.length-1]+w < n) {
            int lastRightLen = n-(stations[stations.length-1]+w);
            if(lastRightLen > 0) {
                answer += lastRightLen / ((2*w)+1);
                if(lastRightLen % ((2*w)+1) != 0)
                    answer++;
            }
        }
        

        return answer;
    }
}