티스토리 뷰

Algorithm

Algorithm) Programmers- 기지국 설치 swift

행복하고 싶은 사람 2022. 12. 2. 13:02

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

아파트 개수(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
}
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/06   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
글 보관함