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

전체 문제 설명

문제 요약

N개의 아파트들이 일렬로 늘어서 있고, 각 아파트에 기지국을 설치할 수 있습니다. 각 기지국에서 송출하는 전파의 도달 거리를 W라고 할 때, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.
N과 W, 그리고 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations이 주어질 때, 기지국을 최소로 증설하면서 모든 아파트에 전파를 전달하려고 합니다. 증설해야할 기지국 개수의 최솟값을 리턴하는 함수를 작성해주세요.

<제한사항>
N: 200,000,000 이하의 자연수
stations의 크기: 10,000 이하의 자연수
stations는 오름차순으로 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수입니다.
W: 10,000 이하의 자연수

예를 들어, 위 그림과 같이, N = 11, stations = [4, 11], W = 1일 때,

이렇게 3개의 기지국을 증설함으로써 모든 아파트에 전파를 전달할 수 있습니다.(3개 미만의 기지국을 증설하여 모든 아파트에 전파를 전달할 수 있는 방법은 없습니다.)

필요조건을 파악하자

완전탐색으로 해결하기 너무 비효율적인 문제거나, 어떻게 문제를 분할해서 적절한 부분문제로 만들지 애매한 경우에는 '해를 구성하는 데 절대 포함하지 말아야 할 값' 혹은 '해를 구성하는 데 무조건 포함해야할 값'을 먼저 구별해 보는 것도 좋습니다. 이 문제에 접근하는 가장 쉬운 방법 또한, 문제의 해가 될 수 있는 필요조건을 파악하는 것입니다.

우선 해답은 반드시 모든 아파트에 전파가 전달되는 상태를 내포해야 합니다. 이런 조건에서 해를 구성하기 위한 필요조건은 무엇일까요. 전체 해답이 무엇일진 아직 모르지만 다음과 같은 사실은 명확히 알 수 있습니다.

첫 번째 기지국의 위치가 (1 + w)번 아파트를 넘어서면 안된다.

만약 첫 번째 기지국이 (1 + w)번 아파트보다 뒤에 설치된다면, 적어도 1번 아파트는 전파를 받지 못할테니 해가 될 수 없습니다. 그러면 첫 번째 기지국의 위치로 가능한 곳은 1번 ~ (1 + w)번 아파트입니다.

그중 (1 + w)번 아파트에 설치된다면, 1번 ~ w번 아파트에 설치될 경우의 전파 도달 범위를 전부 커버하면서도, 뒤로 더 많은 아파트에 전파를 전달할 수 있으니 (1 + w)번에 설치하는 것이 최적입니다.

그러나 만약, 초기에 설치되어 있는 기지국 중 (1 + w)번보다 앞선 번호의 아파트에 설치되어 있는 기지국이 있다면, 어쩔 수 없이 해당 기지국을 첫 번째 기지국으로 삼아야합니다.

이로써, 첫 번째 기지국의 위치는 min(stations[0], 1 + w)로 정해졌습니다. 그렇다면 이제 i번째 기지국의 위치에 대해서 생각해 볼 수 있습니다.

i번째 기지국 위치에 대한 제약조건도 첫 번째 기지국의 위치를 선택할 때와 크게 다르지 않습니다.

i번째 기지국은 ( i - 1 )번째 기지국으로부터 ( 2w + 1 ) 거리 이내에 위치해야 합니다.

두 기지국 간 거리차가 ( 2w + 2 ) 이상으로 벌어지는 순간 전파를 못받는 아파트가 하나 이상 발생하기 때문입니다. 이 경우에도 역시 최적의 위치는 ( i - 1 )번째 기지국으로부터 ( 2w + 1 )만큼 떨어진 위치입니다. 하지만 역시 마찬가지로, ( i - 1 )번째 기지국과 이 기지국으로부터 ( 2w + 1 )만큼 떨어진 거리 이내에, 기존에 설치된 기지국 station[j]가 존재한다면 station[j]를 i번째 기지국으로 삼아야 합니다.

정리하면 다음과 같습니다.

1. 첫 번째 기지국

• min( stations[0], 1 + w )

2. i번째 기지국

• min( station[j], loc[i - 1] + 2w + 1 )
  (단, station[j]는 loc[i - 1]보다 뒤에 위치한 stations 중 최소 인덱스를 가지는 station)

이렇게 절대 해가 될 수 없는 경우를 제외해 가면서, 적절한 해를 구성하기 위한 필요조건을 하나씩 충족해 나가다보면 답을 구할 수 있습니다.

다만, 구현 과정에서 마지막 기지국의 설치 위치를 체크하는 부분에서의 실수만 주의하면 될 것 같습니다.
만약 어떤 기지국 i의 최적 설치 위치(nextStatoin)가 (n + w)를 초과한다면 (i - 1)번째 기지국이 n번 아파트까지 전파를 전달할 수 있다는 것을 의미하지만, i번째 기지국의 설치 위치가 (n + w) 이하로 계산된다면, (i - 1)번째까지의 기지국으로는 전체 아파트를 커버하지 못한다는 뜻이므로 기지국을 n번 아파트에 증설해야 합니다.

코드

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int nextStation = w + 1;
        
        for(int station : stations){
            while(station > nextStation){
                answer++;
                nextStation += w * 2 + 1;
            }
            nextStation = station + w * 2 + 1;
        }
        
        while(nextStation <= n + w){
            answer++;
            nextStation += w * 2 + 1;
        }
        
        return answer;
    }
}