Algorithm) Programmers- 기지국 설치 swift

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

프로그래머스

아파트 개수(N)이 최대 200,000,000이기에 시간을 신경써야합니다

처음에는 전파가 닿지 않는 곳의 길이를 구하려고 배열을 썼다가 시간초과가 났었습니다

 

기지국이 설치되면 -w, +w 에 자기까지 2w + 1 의 영향을 가집니다

그래서 문제 풀이 순서는 이렇습니다

1. 전파가 도달하지 않는 부분의 길이를 계산합니다

2. 그 길이를 2*w+1 로 나누고 올림 해서 ans에 더해줍니다

계산도 바로바로 안하면 시간초과나더라구요 

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var tmp = 1
    var ans = 0
    
    for station in stations {
        ans += Int(ceil((Double(station - w - tmp) / Double(2 * w + 1))))
        tmp = station + w + 1
    }
    if tmp <= n {
        ans += Int(ceil((Double(n - tmp + 1) / Double(2 * w + 1))))
    }
    return ans
}