[프로그래머/Java] 기지국 설치 (Lv. 3)

 

 

문제풀이

 

나는 최대한 시간이 짧게 구현하고 싶어서 전체 아파트의 개수만큼 반복하는 것이 아니라, 이미 설치된 기지국의 위치를 기준으로 필요한 부분만 집중해서 기지국을 설치하도록 구현했다.

첫번째 입출력 예로 예를 들어보면서 설명을 하겠다.

 

 

• 아파트 개수: n = 11
• 이미 설치된 기지국 위치: stations = [4, 11]
• 기지국의 전파 도달 범위: w = 1

 

1. 현재 4번째, 7번째 아파트에 기지국이 설치가 되어있다.

 

 

 

2. 각 기지국이 전파를 양쪽으로 w=1 칸 씩 전달할 수 있으므로 아래와 같이 3,5,10번째 아파트에는 기지국이 설치되지 않아도 된다.

 

 

3. 이제 나머지 아파트들 중 어느 아파트에 기지국을 설치해야하는지가 문제인데

여기서 포인트는 한 기지국을 기준으로 왼쪽 아파트들만 확인하는 것이다.

 

 

4. 어느 한 아파트에 기지국을 설치하게 된다면 그 아파트로부터 도달하는 전파는 2 * w + 1이다.

예시에서는 w=1이므로 기지국 하나 당 커버할 수 있는 아파트의 개수는 3개이다.

 

하지만 6,7,8,9번째 아파트는 총 4개이므로 어느 곳에 설치해도 적어도 한 개의 아파트는 전파가 도달하지 않는다.

 

 

5. 즉, 적어도 6,7,8,9번째 아파트 중에 2개의 기지국을 설치해야한다는 의미이다.

이를 식으로 설명하면  6번째 ~ 9번째 아파트까지 총 4개의 아파트가 있고,

한 기지국이 커버할 수 있는 범위는 2 * w + 1 = 3이므로

4개의 아파트를 3으로 나눈 몫을 구하고,

만약 나머지가 있으면 그 나머지를 커버하기 위해 기지국 1개를 추가로 설치해야한다.

 

만약에 6,7,8번째 아파트까지만 있고, 전파가 w=1이라면

7번째 아파트에 기지국을 설치하면 6,8번째까지 전파가 도달하기 때문에 이 때는 기지국을 1개만 설치할 수 있다.

이는

3개의 아파트를 3으로 나눈 몫이 1이고,

나머지는 0 이기 때문에 기지국을 추가로 설치할 필요가 없는 것이다.

 

 

6. 주의할 점이 한가지 더 있다.

첫번째 구간과 마지막 구간은 따로 처리를 해줘야한다는 점이다.

 

 

코드 설명

int answer = 0; // 필요한 기지국의 총 개수
int range = 2 * w + 1; // 기지국 하나가 커버할 수 있는 범위

1. 기지국 하나가 커버할 수 있는 범위는 2 * w + 1이다.

2를 곱하는 이유는 양쪽으로 전파하기 때문이고, 1을 더하는 이유는 기지국이 설치된 아파트를 의미한다.

 

for (int i = 1; i < stations.length; i++) {
    int end = stations[i] - w;
    int start = stations[i - 1] + w;
    if (end <= start) continue; // 이미 전파가 도달하는 경우 패스
    answer += (end - start - 1) / range; // 구간을 range로 나눠 필요한 기지국 수 계산
    if ((end - start - 1) % range != 0) answer++; // 나머지가 있으면 추가 기지국 필요
}

2. 1부터 stations의 길이까지 반복한다.

이 부분은 이미 설치된 기지국 사이의 구간을 처리하는 부분이다.

end = stations[i] - w는 현재 기지국에서 전파가 닿는 가장 왼쪽 아파트의 번호이다.

start = stations[i - 1] + w는 이전 기지국에서 전파가 닿는 가장 오른쪽 아파트의 번호이다.

 

이 두 값을 비교해, 만약 전파가 서로 겹쳐지거나 닿아있는 경우(end <= start)에는 추가 기지국이 필요하지 않으므로, 다음 반복으로 넘어간다.

 

만약 전파가 닿지 않는 구간이 있다면 그 구간에서 필요한 기지국의 개수를 계산한다.

구간의 길이를 range로 나누고, 나머지가 있다면 기지국을 하나 더 설치한다.

 

예를 들어, 전파가 닿지 않는 구간이 4칸이면 4 / 3 = 1개의 기지국이 필요하고, 나머지가 있으므로 answer++로 추가 기지국을 하나 더 설치한다.

 

if (stations[0] - w > 1) {
    answer += (stations[0] - w - 1) / range;
    if ((stations[0] - w - 1) % range != 0) answer++;
}

3. 이 부분은 첫번째 기지국 이전의 구간을 처리하는 부분이다.

첫 번째 기지국이 w만큼 전파를 발신할 수 있기 때문에 첫 번째 기지국보다 왼쪽에 전파가 닿지 않는 구간이 있을 수 있다.

 

 

stations[0] - w는 첫 번째 기지국이 전파를 발신할 수 있는 가장 왼쪽 아파트 번호이다.

만약 이 값이 1보다 크다면, 첫 번째 기지국 이전에 전파가 닿지 않는 아파트들이 있다는 의미이다. 이 구간을 처리하기 위해, 필요한 기지국의 수를 계산해 추가한다.

 

if (stations[stations.length - 1] + w < n) {
    answer += (n - stations[stations.length - 1] - w) / range;
    if ((n - stations[stations.length - 1] - w) % range != 0) answer++;
}

 

4. 이 부분은 마지막 기지국 이후의 구간을 처리하는 부분이다.

마지막 기지국이 양쪽으로 전파를 발신할 수 있으므로, 마지막 기지국보다 오른쪽 아파트에 전파가 닿지 않을 수 있다.

 

stations[stations.length - 1] + w는 마지막 기지국이 전파를 발신할 수 있는 가장 오른쪽 아파트 번호이다.

만약 이 값이 n보다 작다면, 마지막 기지국 이후의 구간에 전파가 닿지 않는 아파트들이 있다는 것이다.

따라서 이 구간에 필요한 기지국을 추가로 계산해준다.

 

return answer;

5. 결과를 반환한다.

 

 

 

이 문제는 알고리즘 스터디에서 1시간 동안 풀었던 문제였다.

물론 나는 1시간 안에 못 풀어서 오후에 다시 풀어봤는데 다행히 목표했던 짧은 실행 시간으로 구현할 수 있었다.

요즘 알고리즘 문제 풀 때, 시간 초과 날까봐 최대한 효율적으로 풀기 위해 노력하느라 공책에 구현 방법 끄적이는 시간만 거의 20분 되는 것 같다.

고려할 부분이 너무 많았어서 머리가 깨질뻔했지만 다양한 반례를 통해 해결할 수 있었다.

내가 참고했던 반례들을 밑에 공유하겠당.

 

5, [1, 2, 3, 4, 5], 1
기댓값 〉0

11, [4, 12], 1
기댓값 〉3

10, [2, 8], 2
기댓값 〉1

13, [3, 7, 11], 1
기댓값 〉4

 

 

코드

import java.util.*;

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int range = 2*w+1;
        
        for(int i=1; i<stations.length; i++){
            int end = stations[i] - w;
            int start = stations[i-1] + w;
            if(end <= start) continue;
            answer += (end - start -1) / range;
            
            if((end - start - 1) % range != 0) answer++;
        }
        
//         처음
        if(stations[0] - w > 0){
            answer += (stations[0] - w - 1) / range;
            if((stations[0] - w - 1) % range != 0) answer++;
        }
        
        
//         마지막
        if(stations[stations.length-1] + w < n){
            answer += (n - stations[stations.length-1] - w) / range;
            if((n - stations[stations.length-1] - w) % range != 0) answer++;
        }
        return answer;
    }
}

 

 

 

 

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

프로그래머스