[프로그래머스] 기지국 설치 (Python)

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

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

N의 범위를 보면 N: 200,000,000 이하의 자연수라 되어있기 때문에 N을 기준으로 풀면 시간 초과가 난다.

따라서 stations을 바탕으로 알고리즘을 생각했다.

해당 기지국의 커버 범위에 따라 추가해야 하는 기지국 값을 answer에 추가해준다.

 

나의 풀이

def solution(n, stations, w):
    start = 1
    answer = 0
    for station in stations:
        if start > n:
            return answer
        end = station-w-1
        if start > end:
            start = station+w+1
            continue
        else:
            counting = end - start + 1
            answer += counting//(2*w+1) if counting%(2*w+1) == 0 else counting//(2*w+1) + 1
            start = station+w+1
    counting = n - start + 1
    answer += counting//(2*w+1) if counting%(2*w+1) == 0 else counting//(2*w+1) + 1
    return answer