[Java] 프로그래머스 - 기지국 설치

프로그래머스 기지국 설치 문제는 아파트에 기지국을 설치해서 모든 아파트에 전파가 닿게 하는 문제다. 난이도는 레벨3이며 그리디 알고리즘을 통해 해결할 수 있다.

 

프로그래머스 - 기지국 설치 문제 정보

알고리즘 분류

- 그리디

난이도

- Level 3

 

문제 요약

• 아파트에 기지국을 설치하려 한다.
  • 아파트 수: N < 2억
  • 전파 거리: W (전파가 닿는 범위는 기지국 기준 -W ~ +W)
  • 이미 설치된 기지국: stations (개수 S < 만)
• Q. 모든 아파트에 전파가 닿기 위해 최소 몇개의 기지국을 추가 설치해야하나?

 

문제 풀이 과정

• N개의 아파트를 일일히 확인하면 안됨 (시간이 타이트함)
• 설치된 기지국들 사이사이 빈 공간에 추가로 몇개씩 넣어야 하는지만 확인

코드

public int solution(int n, int[] stations, int w) {
    int answer = 0;
    int signalWidth = w * 2 + 1;
    int lastSignal = 0; // 가장 마지막으로 전파가 닿은 곳

    for (int station : stations) {
        // 현재 기지국이 닿기 직전의 위치 (왼쪽)
        int noSignal = station - w - 1;

        // 전파가 닿지 않는 곳이 존재하는 경우
        if (lastSignal < noSignal) {
            // 전파가 안 닿는 길이에 필요한 기지국 수를 구함
            answer += getStationNumber(signalWidth, lastSignal, noSignal);
        }
        lastSignal = station + w;
    }

    // 맨 뒷부분 처리
    if (n - lastSignal > 0) {
        answer += getStationNumber(signalWidth, lastSignal, n);
    }

    return answer;
}

private int getStationNumber(int signalWidth, int lastSignal, int noSignal) {
    int div = (noSignal - lastSignal) / signalWidth;
    int mod = (noSignal - lastSignal) % signalWidth;
    return mod == 0 ? div : div + 1;
}

• 시간복잡도: O(S)
  • 빈 공간에 필요한 기지국 수를 구하는 getStationNumber() 메소드를 Math.ceil()을 이용해서 풀었을 때 마지막 TC 시간초과 남. 아마 내부적으로 연산이 복잡한 듯. 그냥 몫과 나머지를 이용하는 방식을 쓰자.
• 공간복잡도: 추가 공간 X