[프로그래머스] 기지국 설치

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

✍️ 첫번째 접근

visited라는 Array에 입력으로 주어진 기지국이 도달할 수 있는 아파트 번호를 true로 저장한다.
아파트는 1번부터 n번까지 있으므로 while문을 돌면서 해당 아파트가 이미 도달할 수 있다면 인덱스를 하나 증가시킨다. 그렇지 않다면, 한개의 기지국은 양방향으로 w만큼의 아파트에 도달할 수 있으므로 해당 범위만큼 visited 배열을 true로 만들면서 answer를 하나씩 추가한다.
하지만, 효율성 테스트에서 시간 초과가 발생하였다.

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var answer = 0
    var visited: [Bool] = Array(repeating: false, count: n+1) // 전파 전달 여부
    for s in stations {
        for i in s-w...s+w {
            if i < 1 || i > n {
                continue
            }
            visited[i] = true
        }
    }
    // start부터 end까지 도달하지 않은 아파트가 있다면 기지국 설치하는 메서드    
    func check(_ start: Int, _ end: Int) {
        if visited[start...end].filter{$0 == false}.count > 0 {
            for j in start...end {
                visited[j] = true
            }
            answer += 1
        }
    }
    
    var idx = 1
    while idx <= n {
        if visited[idx] {   // 이미 도달한 아파트이면 다음 아파트로 이동
            idx += 1
            continue
        }
        else {  // check 메서드에서 for문 범위 예외 처리를 위해 if문으로 범위 처리
            idx += w    // idx에서 양방향으로 w만큼 전파가 도달할 수 있으므로
            if idx-w < 1 {
                check(1,idx+w)
            }
            else if idx+w > n {
                check(idx-w,n)
            }
            else {
                check(idx-w,idx+w)                
            }
        }
    }

    return answer
}

✍️ 두번째 접근

아래 해설을 참고하여 해결할 수 있었다.
https://school.programmers.co.kr/questions/27785
n이 최대 200,000,000으로 충분히 크고 한번에 할 수 있는 연산을 생각해내지 못했기 때문에 시간 초과가 발생한 거 같았다.
문제를 단순화하는 것을 항상 염두에 두어야겠다.

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var answer = 0
    var start = 1   // 1번 아파트부터 시작
    var end = 0
    for s in stations {
        end = s-w-1 // 현재의 기지국에서 왼쪽 방향으로 도달하지 못한 아파트 위치
        if end >= start {   // 도달하지 못한 아프트가 존재
            let length = end-start+1    // 길이 저장
            if length <= 2*w+1 {    // 한개의 기지국으로 커버할 수 있을 경우
                answer += 1
            }
            else {
                answer += Int(ceil(Double(length)/Double((2*w+1))))
            }
        }
        start = s+w+1   // 현재의 기지국에서 오른쪽 방향으로 도달하지 못한 아파트 위치로 갱신
    }
    // n이 start보다 크거나 같다면, 아직 도달하지 못한 아파트가 존재한다는 의미
    if n >= start {
        let length = n-start+1
        if length <= 2*w+1 {
            answer += 1
        }
        else {
            answer += Int(ceil(Double(length)/Double((2*w+1))))
        }        
    }
    return answer
}