문제 요약
N개의 아파트가 일렬로 있고, 일부 아파트에는 이미 기지국이 설치되어 있다.
기지국 하나는 설치된 위치를 기준으로 왼쪽 W칸, 오른쪽 W칸까지 전파를 전달할 수 있다.
이미 설치된 기지국으로 전파가 닿지 않는 아파트가 있을 때, 모든 아파트에 전파가 닿도록 추가로 설치해야 하는 기지국의 최소 개수를 구해야 한다.
핵심 아이디어
기지국 하나가 커버할 수 있는 아파트 수는 다음과 같다.
2 * W + 1이미 설치된 기지국들이 커버하는 구간을 기준으로, 전파가 닿지 않는 빈 구간의 길이를 구한다.
각 빈 구간마다 필요한 기지국 수는 다음과 같이 계산할 수 있다.
ceil(빈 구간 길이 / 기지국 하나의 커버 길이)Python에서는 올림 나눗셈을 다음과 같이 구현할 수 있다.
(length + coverage - 1) // coverage풀이 과정
1. 기지국 하나의 커버 범위 계산
coverage = 2 * w + 1기지국을 하나 설치하면 최대 coverage개의 연속된 아파트에 전파를 전달할 수 있다.
2. 아직 전파가 닿지 않은 시작 위치 관리
start는 현재 확인해야 하는 첫 번째 아파트 번호를 의미한다.
처음에는 1번 아파트부터 확인한다.
start = 13. 기존 기지국의 커버 구간 확인
기존 기지국이 station 위치에 있다면, 해당 기지국이 커버하는 구간은 다음과 같다.
station - W ~ station + W따라서 현재 start부터 station - W - 1까지는 전파가 닿지 않는 구간이다.
이 구간의 길이는 다음과 같다.
length = (station - w) - start이 길이가 양수라면, 해당 구간에 추가 기지국을 설치해야 한다.
4. 마지막 빈 구간 처리
모든 기존 기지국을 확인한 뒤에도 start가 N 이하라면, 마지막까지 전파가 닿지 않는 구간이 남아 있는 것이다.
if start <= n:
length = n - start + 1이 구간에 대해서도 필요한 기지국 수를 더한다.
Python 코드
def solution(n, stations, w):
answer = 0
coverage = 2 * w + 1
start = 1
for station in stations:
left = station - w
right = station + w
if start < left:
length = left - start
answer += (length + coverage - 1) // coverage
start = right + 1
if start <= n:
length = n - start + 1
answer += (length + coverage - 1) // coverage
return answer코드 설명
coverage
coverage = 2 * w + 1기지국 하나가 커버할 수 있는 아파트의 최대 개수다.
예를 들어 w = 2라면 왼쪽 2칸, 자기 자신, 오른쪽 2칸을 포함하므로 총 5칸을 커버한다.
start
start = 1아직 전파 커버 여부를 확인하지 않은 가장 왼쪽 아파트 번호다.
기존 기지국의 커버 구간을 만날 때마다, start를 해당 커버 구간의 오른쪽 다음 위치로 이동시킨다.
빈 구간 길이 계산
if start < left:
length = left - start기존 기지국이 커버하는 왼쪽 경계가 left라면, start부터 left - 1까지는 전파가 닿지 않는다.
이 빈 구간에 필요한 기지국 수를 계산한다.
올림 나눗셈
answer += (length + coverage - 1) // coverage빈 구간 길이가 coverage로 딱 나누어떨어지지 않으면 기지국이 하나 더 필요하다.
따라서 올림 나눗셈을 사용한다.
마지막 구간 처리
if start <= n:
length = n - start + 1모든 기존 기지국을 확인한 뒤에도 남은 아파트가 있다면, 마지막 빈 구간을 처리한다.
시간 복잡도
기존 기지국 배열 stations를 한 번만 순회한다.
기존 기지국 수를 s라고 하면 시간 복잡도는 다음과 같다.
O(s)N이 매우 클 수 있어도 모든 아파트를 하나씩 확인하지 않기 때문에 효율적이다.
공간 복잡도
추가 배열을 사용하지 않고 변수만 사용한다.
O(1)정리
이 문제는 모든 아파트를 직접 순회하지 않고, 전파가 닿지 않는 구간만 계산하는 것이 핵심이다.
풀이 흐름은 다음과 같다.
기존 기지국의 커버 구간 확인
커버되지 않은 빈 구간 길이 계산
빈 구간마다 필요한 기지국 수를 올림 나눗셈으로 계산기지국 하나가 커버하는 길이 2 * W + 1만 잘 활용하면 간단한 그리디 방식으로 해결할 수 있다.
