[파이썬] 기지국 설치

문제 설명

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

프로그래머스

문제 풀이

• n의 최댓값이 2억인데 채점 시 효율성 테스트까지 거치므로 시간 복잡도는 O(n)을 넘으면 안됨
• n을 순회하기 보단 길이가 1만 이하인 stations를 활용해서 수학적으로 접근
• 한 지점에서 커버 하는 공간은 2*w + 1 이다. (좌우 + 자기 자신)
• 길이가 10이고 w가 1이면 10//3 을 통해 4개가 필요한 걸 알 수 있음
• stations이 이미 있으므로 이것을 제외하고 좌우를 생각
• 만약 stations이 차지하고 있는 왼쪽보다 1보다 작다면 왼쪽에는 추가 할 필요가 없음
• 기준점(start)에는 오른쪽 차지한 영역 이 후 값을 저장 
• sations을 모두 정리했는데도 기준점이 n보다 작을 경우 남은 구간은 width로 나누면 됨(ceil을 통해 나머지가 있을 경우 자동으로 +1 해줌) 

소스 코드

 

from math import ceil
def solution(n, stations, w):
    answer = 0
    width = w*2+1
    start=1
    for s in stations:
        answer+=max(ceil((s-w-start)/width),0)
        start=s+w+1
    if n>=start:
        answer+=ceil((n-start+1)/width)
    
    
    return answer

print(solution(11,[4,11],1))