(Swift) Programmers 기지국 설치

SteadySlower·2023년 2월 24일

greedy programmers swift

Coding Test

목록 보기

222/305

코딩테스트 연습 - 기지국 설치

아파트를 순회하는 풀이: O(N), N은 최대 200,000,000

문제 풀이 아이디어

1번 아파트부터 순회하면서 그리디 알고리즘을 활용해서 풀면 됩니다. 총 4가지 케이스가 있습니다.

현재의 아파트가 전파가 닿지 않을 때
1. 왼쪽에 (= 번호가 더 낮은 아파트에) 전파가 닿지 않는 w개의 아파트가 있다면 현재 위치에 무조건 기지국을 세워야 합니다.
2. 왼쪽에 전파가 닿지 않는 아파트가 w개 미만이라면 아직 기지국을 세우지 않아도 됩니다.
현재의 아파트에 전파가 닿을 때
1. 왼쪽에 전파가 닿지 않는 아파트가 1개라도 있다면 기지국을 하나 무조건 세워야 합니다.
2. 왼쪽에 전파가 닿지 않는 아파트가 없다면 기지국을 세울 필요가 없습니다.

모든 케이스를 보면 오른쪽에 (= 번호가 더 높은 아파트) 기지국이 있는지 없는지, 전파가 닿는지 닿지 않는지는 고려할 사항이 아닙니다. 즉 미래 상황을 생각하지 않고 지금 당장 필요한 선택을 하는 그리디 알고리즘의 정의와 부합합니다.

코드

// O(N)의 시간복잡도를 가진 풀이
func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    // 필요한 기지국의 갯수
    var ans = 0

    // 아파트를 배열로 (신호가 닿으면 true, 닿지 않으면 false)
    var apts = Array(repeating: false, count: n + 1)
    
    // 기지국이 커버하는 범위를 apts에 표시한다.
    for station in stations {
        let coverage = (station - w...station + w)
        for i in coverage {
            // apt의 범위를 벗어나지 않는지 체크
            if 1..<(n + 1) ~= i { apts[i] = true }
        }
    }

    // index의 왼쪽에 남아 있는 전파가 닿지 않는 apt의 갯수
    var left = 0
    // 현재의 아파트 위치
    var index = 1

    // 아파트를 순회하면서 필요할 때마다 기지국을 세우기
    while index < n + 1 {
        // 현재 아파트가 전파가 닿지 않을 때
        if apts[index] == false {
            // 왼쪽에 w만큼의 전파가 닿지 않는 아파트가 있는 경우 -> index 위치에 기지국을 세운다.
            if left == w {
                index += w + 1 //👉 index 위치에 세우면 오른쪽 w개 만큼 커버가 되므로 index를 그 다음으로 이동
                ans += 1 //👉 기지국 1개 추가
                left = 0 //👉 index 위치에 기지국을 세웠으므로 전파가 닿지 않는 아파트 0개
            // 왼쪽에 전파가 닿지 않는 아파트가 w개 미만인 경우 -> 나중에 세워도 된다.
            } else {
                left += 1
                index += 1
            }
        // 현재 아파트에 전파가 닿을 때
        } else {
            // 왼쪽에 전파가 닿지 않는 아파트가 1개라도 있는 경우 -> 기지국이 1개 필요함
            if left != 0 {
                index += w + 1
                ans += 1
                left = 0
            // 왼쪽에 전파가 닿지 않는 아파트가 없는 경우 -> 기지국 필요 없음
            } else {
                index += 1
            }
        }
    }
    
    // 모든 index 끝까지 갔는데 전파가 닿지 않는 아파트가 남은 경우 -> 기지국 1개 필요함
    if left != 0 { ans += 1 }

    return ans
}

🚫 효율성 테스트를 통과할 수 없음…

이 코드의 시간복잡도는 O(N)입니다. 하지만 N이 최대 200,000,000으로 O(N)의 알고리즘으로 통과하기에도 부담이 되는 크기입니다. 아니나 다를까 효율성 테스트는 통과할 수 없었습니다. 하지만 이 문제는 O(N)보다 더 효율적인 알고리즘으로 풀 수는 없는 문제입니다.

알고리즘을 효율적으로 할 수 없다면 방법은 단 하나 뿐입니다. 바로 더 작은 N을 찾는 것입니다.

기지국을 순회하는 풀이: O(N), N은 최대 10,000

문제 풀이 아이디어

모든 아파트를 순회하지 않고 기지국을 순회하면서 문제를 풀어보도록 하겠습니다. 각각의 기지국을 순회하는 반복문을 사용하는 방법입니다. 원리는 마찬가지로 그리디 알고리즘입니다.

현재 기지국을 기준으로 왼쪽 (= 번호가 작은 아파트들)에 전파가 닿지 않는 아파트가 몇개 있는지 구합니다. 그리고 그 아파트를 커버하기 위해서 필요한 기지국의 갯수를 세서 세웁니다.

마지막 기지국까지 순회했는데 아직 모든 아파트가 커버되지 못했다면 필요한 기지국의 갯수를 세서 더해주면 됩니다.

코드

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    // 기지국 갯수
    var ans = 0
    // 하나의 기지국이 커버할 수 있는 범위
        //👉 ceil(올림)을 사용하기 위해서 Double로 캐스팅
    let coverage = Double(w * 2 + 1)
    
    // 지금까지 순회한 기지국이 커버하지 못하는 가장 첫 아파트
        //👉 현재 기지국 순회 전이므로 가장 처음 아파트
    var now = 1

    // 기지국을 순회하면서
    for s in stations {
        // 현재 기지국과 이전 기지국 사이에 존재하는 전파가 닿지 않는 아파트의 갯수 (현재 기지국 기준으로 왼쪽)
            //👉 ceil(올림)을 사용하기 위해서 Double로 캐스팅
        let left = Double(s - w - now)
        
        // 필요한 기지국의 갯수 더하기
            //👉 (전파 없는 아파트 갯수 / 하나의 기지국의 커버 범위)를 올림한 것
        ans += Int(ceil(left / coverage))
        
        // 현재의 기지국이 커버할 수 범위보다 하나 오른쪽에 있는 아파트
        now = s + w + 1
    }

    // 모든 기지국을 순회했을 때 아직 커버하지 못하는 아파트가 남아 있다면 (마지막 기지국 기준으로 오른쪽)
    if n >= now {
        // 필요한 만큼 기지국을 세운다
        let right = Double(n - now + 1)
        ans += Int(ceil(right / coverage))
    }

    return ans
}