문제
접근
station의 위치가 정렬된 채로 들어오기 때문에 따로 전처리 해줄 필요는 없다.
우선 전파의 거리 range를 구해놓자.
자기 자신과 좌, 우로 전달되므로 range = w * 2 + 1 이 될 것이다.
이제 정렬된 스테이션을 하나씩 보면,
station의 위치를 x라고 하면 처음은 1번 아파트부터 x-w 아파트까지는 전파가 들어오지 않을 것이다.
이 범위에 range가 몇 번들어가면 될지 계산해주면된다.
그리고 시작 위치를 x+w로 옮겨주고 같은 작업을 반복하면된다.
그리고 마지막 station까지 검사했다면 이제 마지막 station에서 n까지만 따로 검사해주면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(n, stations, w):
answer = 0
starti = 1
ran = w*2 + 1
for station in stations:
answer += (station - w - starti) // ran
if (station - w - starti) % ran > 0:
answer += 1
starti = station + w + 1
if starti <= n:
answer += (n + 1 - starti) // ran
if (n + 1 - starti) % ran > 0:
answer += 1
return answer