[Python] 프로그래머스 Lv3. 기지국 설치

문제

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

프로그래머스

문제 요약

일렬로 있는 아파트에 기존 기지국들이 설치되어 있고, 각 기지국은 양쪽으로 w만큼 전파를 전달할 수 있다.

전파가 닿지 않는 모든 아파트에 전파가 전달되도록 최소한의 기지국을 추가로 설치하면 되는 문제다.

---

풀이

기지국 하나가 커버할 수 있는 범위는 2 * w + 1이다.

 

기존 기지국을 순서대로 확인하면서 전파가 닿지 않는 구간의 길이를 구하고,

해당 구간에 필요한 기지국의 개수를 계산하면 된다.

 

구간의 길이가 gap, 기지국 하나의 범위가 cover라면 필요한 기지국의 개수는 올림 계산으로 구할 수 있다.

(gap + cover - 1)

 

기존 기지국 앞쪽의 빈 구간들을 계산한 뒤, 마지막 기지국 이후에 남은 구간도 한 번 확인한다.

def solution(n, stations, w):
    ans = 0
    cover = 2 * w + 1
    start = 1

    for station in stations:
        end = station - w

        if start < end:
            gap = end - start
            ans += (gap + cover - 1) // cover

        start = station + w + 1

    if start <= n:
        gap = n - start + 1
        ans += (gap + cover - 1) // cover

    return ans

시간복잡도

기존 기지국의 개수를 m이라고 했을 때 stations를 한 번 돌기 때문에 O(m)이다.

아파트 전체 n개를 직접 확인하지 않기 때문에 n이 커도 효율적으로 처리할 수 있다.