Programmers - 기지국 설치

문제 링크

처음에 든 생각은 전파가 닿지 않는 첫 아파트가 끝에 닿게 설치하면서 업데이트 하는 방법이었는데
n <= 2억 을 확인하고 시간초과가 발생할 것이라고 생각해서 다른 풀이 방법을 생각해보았다.

다 전파가 닿지 않을 때는 O(1)로 필요한 설치 개수를 구할 수 있다. (get_required_stations)
1번 예시에서 결국 구해야 할 것은

1. 전파가 닿지않는 2개 아파트
2. 전파가 닿지않는 4개 아파트 

를 각각 계산하는 것과 다를 바 없다는 것을 알았다.
하나의 남은 부분의 어느 곳에 기지국을 설치해도 다른 남은 부분에 영향을 주지 않기 때문이다.
ex) 1번 예시에서 [1,2] , [6,7,8,9] 가 각각 남은 부분 일 때, 2에 설치해도 [6,7,8,9]에는 영향을 주지 않는다.

stations의 길이는 최대 1만이니 이 방법을 이용하면 O(10000)에 풀이 가능하다.

def solution(n, stations, w):

    def get_required_stations(n):
        result = 0
        coverage = (2*w)+1
        result += n//coverage
        result = result if n % coverage == 0 else result+1
        return result

    current = 1
    remains = []
    for station in stations:
        st = station - w
        ed = station + w
        if current < st:
            remains.append(st - current)
        current = ed+1

    if current <= n:
        remains.append(n+1-current)

    requires = list(map(get_required_stations, remains))
    return sum(requires)