[스위프트 알고리즘] 기지국 설치

문제

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

코딩테스트 연습 - 기지국 설치

 

문제 설명

N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

• 초기에, 1, 2, 6, 7, 8, 9번째 아파트에는 전파가 전달되지 않습니다.

• 1, 7, 9번째 아파트 옥상에 기지국을 설치할 경우, 모든 아파트에 전파를 전달할 수 있습니다.

• 3개의 아파트보다 더 많은 아파트 옥상에 기지국을 설치할 경우에도 모든 아파트에 전파를 전달할 수 있습니다.

이때, 우리는 기지국을 최소로 설치하면서 모든 아파트에 전파를 전달하려고 합니다. 위의 예시에선 최소 3개의 아파트 옥상에 기지국을 설치해야 모든 아파트에 전파를 전달할 수 있습니다.

아파트의 개수 N, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열 stations, 전파의 도달 거리 W가 매개변수로 주어질 때, 모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값을 리턴하는 solution 함수를 완성해주세요

제한사항

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

풀이

제한 사항을 보면 이 문제는 O(N)으로도 풀면 안된다는 것을 알 수 있습니다. 무조건 O(1)이나 O(nlogn)으로 풀어야 할 것 같습니다. 처음에는 너무 전형적인 이분탐색 스타일의 문제이길래, 이분탐색으로 풀이를 해보려고 했는데 미리 설치되어있는 기지국이 있기 때문에 기지국을 설치해보는 추가적인 연산이 요구되면서 문제를 해결할 수 없었습니다. 

 

그래서 끙끙대다가 질문하기 탭을 통해 힌트를 얻어 그리디한 방법으로 해결하게 되었습니다. 

 

기지국의 전파거리 w를 이용하면 각 위치에 있는 기지국이 전파를 보낼 수 있는 최대 범위가 2 * w + 1 이라는 것을 알 수 있습니다. 즉, 최소한 적은 개수의 기지국을 설치하기 위해서는 2 * w + 1 만큼의 범위를 두고 기지국이 설치되어야 한다는 것입니다. 

 

따라서 현재 주어진 기지국의 위치를 통해 전파가 닿지 않는 아파트 구간을 선별하고 해당 구간 안에 설치할 수 있는 최소 기지국 개수를 구해주면 문제를 해결할 수 있습니다. 시작위치를 첫번째 아파트로 잡고 이미 설치된 기지국을 하나씩 체크하면서 구간을 설정하고, 만약 마지막 기지국의 범위가 마지막 아파트까지 닿지 않는다면, 마지막 기지국의 범위에서부터 마지막 아파트까지의 구간에 대한 계산까지 해주면 됩니다.

코드