[프로그래머스] / [Level 3] / [Python] 기지국 설치

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

프로그래머스

---

N의 크기가 2억 이하의 자연수이기 때문에 하나씩 탐색을 하게되면 시간초과를 출력한다.

따라서 제공되는 stations에 포함되지 않는 수의 개수를 계산해서 결과를 출력하도록 하였다.

 

N:11,    설치되어 있는 기지국:[4, 11],    W:1

이와 같은 경우 추가로 설치할 수 있는 '구역'은 1~2, 6~9 이다. 해당 범위의 개수인 2, 4를 (1+w*2)로 나눈 몫이 설치할 수 있는 기지국의 갯수가 된다 (나머지가 있는 경우 + 1).

 

stations의 시작과 끝을 start, end 변수에 담았고, 사이의 영역의 개수를 구하기 위해 before 변수를 함께 사용했다.

def solution(n, stations, w):
    answer = 0
    
    before = 0
    
    for station in stations:
        start, end = station - w, station + w
        
        if start < 0: start = 0
        if end > n: end = n
        
        cnt = start - before - 1
        if cnt > 0:
            if cnt % (1+w*2) == 0:
                answer += int(cnt/(1+w*2))
            else:
                answer += int(cnt/(1+w*2)) + 1
            
        before = end
    else:
        if end != n:
            cnt = n - before
            if cnt % (1+w*2) == 0:
                answer += int(cnt/(1+w*2))
            else:
                answer += int(cnt/(1+w*2)) + 1


    return answer