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

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

프로그래머스

 

 

난이도 

LV 3

 

 

문제 설명 

아파트 N개가 주어지고 아파트 옥상에 기지국이 설치되어있다. 

해당 기지국의 범위가 w로 변경되면서 기지국을 추가로 설치해야하는데, 이때 최소로 설치하는 기지국의 개수를 return해줘야한다.

기지국 설치 아파트기준으로 양쪽으로 w만큼 전달 할 수 있다.

ex_) 만약 4번 아파트에 w가 2라면 2,3,4,5,6 번의 아파트를 해당 기지국으로 커버할 수 있다.

 

 

접근법

모든 아파트 n번을 탐색하기에 주어지는 N이 200,000,000이하의 자연수 이므로 효율성에서 시간초과가 발생한다.

따라서 기존에 설치된 기지국이 주어지는 번호 기준으로 기존 기지국이 커버할 수 있는 아파트 (양쪽으로 w만큼)을 제외해고 w*2+1로 나누어 주면 해당 범위 사이에 기지국이 몇개 설치 되야하는지 알 수 있다.

이때 모든 아파트가 기지국범위 안에 들어가야하기 때문에 math.ceil을 이용해서 올림을 해주면 해당 범위 사이에 필수적으로 필요한 기지국의 개수를 알 수 있다.

마지막 기지국으로부터 아파트의 끝까지 추가로 기지국이 필요한 개수를 확인후 값을 return해주면 된다.

 

 

코드

import math
def solution(n, stations, w):
    answer = 0
    idx = 1
    for s in stations:
        answer += math.ceil(((s-w) - idx) / ((w*2)+1))
        idx =  s+w+1
    
    answer += math.ceil((n+1 - idx) / ((w*2)+1))
    
    return answer

---