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

풀이

해설

이 문제는 전파가 닿지 않는 기지국의 범위 안에 모든 아파트에 전파를 전달하기 위해선, 몇개의 기지국이 설치되어야 하는가에 대한 값을 찾는 문제이다.

값을 찾기 위해 필요한 것은 다음과 같다.

 

1. 전파가 닿지 않는 아파트의 범위
2. 해당 범위들에 필요한 기지국의 수를 구하는 방법

전파가 닿지 않는 아파트의 범위

문제에선 stations 배열로 이미 설치된 기지국의 위치가 주어진다. 따라서 해당 위치를 기준으로 기지국의 전파 범위인 w를 빼거나 더해 범위를 구할 수 있다.

 

1(첫번째 아파트)부터 station - w까지 기지국이 설치되지 않았다고 가정한다면, 첫번째 범위는 station - w - 1이라고 볼 수 있다. 이제 해당 범위의 필요한 기지국의 수를 구하면 된다.

 

이후엔 기준을 station + w + 1로 해주어 다음 범위를 추적할 수 있게 초기화한다.

 

추가적으로 한가지의 예외처리가 필요한데, 범위의 시작 부분부터 기지국이 존재할 수 있으니, station - w가 범위의 시작 위치보다 큰 상태여야 한다.

int right = station - w;

if (left < right) {
    ...
}

위와 같이 예외를 잡을 수 있다.

해당 범위들에 필요한 기지국의 수를 구하는 방법

answer += (right - left) / (w * 2 + 1);
if ((right - left) % (w * 2 + 1) != 0) {
    answer++;
}

 

범위에 대한 기지국 수를 구하는 방법은 범위 / w2 + 1과 같다. 하나의 기지국은 전파되는 범위 w가 왼쪽, 오른쪽에 퍼지기 때문에 2를 곱해주고, 기지국이 세워지는 위치 값 1을 더해준다.

 

이것을 범위에 나눠주면 필요한 기지국 수를 구할 수 있으며 나머지 값이 있다면 +1을 해줘야 한다. 모든 아파트에 전파를 전달해야 하기 때문에 겹치는 부분이 있어도 추가를 해줘야 한다.

마지막 범위 처리

if (left < n + 1) {

    answer += (n + 1 - left) / (w * 2 + 1);

    if ((n + 1 - left) % (w * 2 + 1) != 0) {
        answer++;
    }
}

station의 왼쪽을 기준으로 범위를 잡기 때문에 for문이 종료되면 마지막 범위를 탐색하진 않는다. 따라서 위와 같은 코드로 마지막 범위를 탐색해 준다.

시간복잡도

stations를 순회하며 로직을 처리한다. stations.length를 N이라고 했을 때, $O(N)$의 시간복잡도를 가진다고 예상한다.

시간복잡도를 구하는 것은 익숙하지 않아서 틀린 값일 수 있다.

코드

package 기지국설치;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;

        int left = 1;
        for (int station : stations) {
            int right = station - w;

            if (left < right) {
                answer += (right - left) / (w * 2 + 1);
                if ((right - left) % (w * 2 + 1) != 0) {
                    answer++;
                }
            }
            left = station + w + 1;
        }

        if (left < n + 1) {
            answer += (n + 1 - left) / (w * 2 + 1);

            if ((n + 1 - left) % (w * 2 + 1) != 0) {
                answer++;
            }
        }

        return answer;
    }
}

Reference

• 문제
• 참고