[Algo Rhythm🕺💃] 프로그래머스 - 기지국 설치

💫문제 분석

아파트의 개수를 $n\ (1 \le n \le 2 \times 10^8)$, 현재 기지국이 설치된 아파트의 번호가 담긴 1차원 배열을 $S\ (1 \lt \left\vert S \right\vert \lt 10^4,\ S는\ 오름차순\ 정렬)$, $S$에 속하는 각 기지국을 $s_i\ (1 \le s_i \le n,\ 1 \le i \le \left\vert S \right\vert )$, 전파의 도달 거리를 $w(1 \le w \le 10^4)$, 한 기지국이 전파를 전달할 수 있는 기지국들의 최개 개수를 $d\ (=2 \times w + 1)$라고 하자.

 

현재 설치된 기지국 $s_i$의 전파 전달 범위를 $rcvd_i$라고 할 때, $rcvd_i$는 다음과 같다.

$\begin{matrix} rcvd_i &=& \left[\ left_i,right_i\ \right] \\ &=& \left[\ \max(1, s_i - w),\min(n, s_i + w)\ \right] \end{matrix}$

 

우린 $rcvd_i$를 통해 기지국이 설치되지 않고 연속된 아파트들의 개수 $L_j$를 알 수 있는데 그것은 다음과 같다.

$L_j = pos - left_i\ (pos : 연속된\ 아파트\ 중\ 첫\ 아파트의\ 번호,\ 0\le j \le i + 1)$

 

또한 우린 $L_j$을 통해 연속된 모든 아파트에 전파를 전달하기 위해 증설해야 하는 기지국 개수의 최솟값인 $N_{stn_j}$를 알 수 있는데 그것은 다음과 같다.

$N_{stn_j} = \begin{cases} 1 &if\ 0 \lt L_j \lt d\ \\\ulcorner {L_j \over d} \urcorner&else\end{cases}​$

 

🔥문제 풀이

모든 아파트에 전파를 전달하기 위해 증설해야 할 기지국 개수의 최솟값 $ans$는 다음과 같다.

$ans = \sum N_{stn_j}$

 

$rcvd_i$를 하나씩 순회하며 $N_{stn_j}$를 구한 뒤 더하면 될 것 같지만 주의해야 할 점이 하나 있다.

그것은 바로 아래와 같이 마지막 $rcvd_i$의 $right_i$가 $n$보다 작은 경우이다.

 

이 경우 마지막 $N_{stn_j}$를 구할 수 없기 때문에 $rcvd$에 $\left[\ n+1,n+1\ \right]$라는 가상의 전파 전달 범위를 추가한다.

 

✨복잡도 분석

$S$와 $rcvd$의 크기를 $n\ (1 \lt n \lt 10^4)$, 이라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

⏰시간 복잡도 : $O(n)$

• $rcvd$ 구하기 : $O(n)$
• $\sum N_{stn_j}$ 계산 : $O(n)$

🏠공간 복잡도 : $O(n)$

• $S,\ rcvd$ 저장 : $O(n)$

 

🌈코드

 

🌏문제 출처

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