프로그래머스. 기지국 설치

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

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

 

아파트의 갯수인 N이 최대 2억이므로 O(N) 이하의 알고리즘으로 풀어야 된다는 계산이 선다.

w가 2라면 station기준 왼쪽 2칸 오른쪽 2칸까지 전파가 닿는데, 

다르게 보면 2-w 부터 2+w까지가 범위라고 볼 수 있다.

 

그렇다면 1번 집부터 전파범위가 닿도록 설치하면 된다.

w가 2라면 총 범위의 크기는 5이므로, 

1번집에 설치했다면 6번집에 설치하고, 11번, 16번 ... 이런식으로 설치하면 된다.

 

그런데 문제는 이미 설치되어 있는 집들이 주어진다는 것인데, 

나는 이 집들의 번호를 큐에 담아서 큐의 front에 있는 집 (즉 이미 설치되 있는집)의 범위에 도달하기 전까지 

기지국을 계속 설치하고, 큐의 front에 있는 집의 범위에 도달했다면 그 범위를 스킵하고 큐에 원소를 pop해 줬다.

이렇게 하다보면 언젠가 큐가 비게되는데 (즉 이미 기지국이 설치 되어있는 모든 집들을 넘어섰다) 

그렇게 되면 남은 집들의수를 기지국의 범위로 나눠주면 나머지 아직 설치되어 있지 않은 집들에 설치해야 하는 기지국의 갯수가 된다.

(물론 나눴을때 딱 떨이지지 않으면 범위를 모두 채우지 않는 기지국 하나를 더 설치해야하므로 +1을 해줘야한다)