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

구현 문제입니다.

건물의 n과 기지국 범위 w가 주어졌을 때, 모든 건물이 기지국 범위에 들어오게 하는 최소 기지국 설치 개수를 구하는 문제입니다.

일차원 배열의 stations의 원소에는 이미 기지국이 설치되어있다고 생각하면 됩니다.

 

처음에는 이진 탐색으로 구현했습니다.

n의 범위가 2억이기 때문에 이진 탐색으로 구현해도 불가능 할 거 같지만, 그 이외에 생각나는 알고리즘이 없었습니다.

하한을 구해 설치의 최소를 구했습니다만, 아니나 다를까 시간초과가 발생했습니다.

// 하한
while(lo<hi){
    mid = (lo+hi)/2;
    if(canInstall(mid)){
        hi = mid;
    }else{
        lo = mid+1;
    }
    return lo
}

 

 

생각해보니, 좌측에서 부터 빈 공간의 크기에서 기지국 범위를 나누면 될 거 같아서 그렇게 구현했습니다.

어이없게도 성공하네요.

stations는 오름차순으로 정렬되어 있다고 문제에 나와있기 때문에, 정렬하지 않았습니다.

 

[구현 코드]

import java.util.Arrays;

class Solution {
    public static int solution(int n, int[] stations, int w) {
        int cnt = 0;
        int range = 0;
        for (int station : stations) {
            int le = station - w;
            int ri = station + w;

            if(range < le){
                // 빈 공간의 크기
                int empty = le - range -1;
                cnt += cntBaseStation(empty, w);
                range = ri;
            }else{
                range = Math.max(ri, range);
            }
        }

        // 기지국 범위가 끝나고, 아직 범위 밖의 건물이 존재할 때
        if(range  < n){
            int empty = n-range;
            cnt += cntBaseStation(empty, w);
        }

        return cnt;
    }

    private static int cntBaseStation(int empty, int w){
        int di = empty/(2*w+1);
        return (empty%(2*w+1)==0) ? di : di+1;
    }
}