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

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

프로그래머스

 

제출한 답안

import Foundation

func solution(_ n: Int, _ stations: [Int], _ w: Int) -> Int {
    var answer = 0
    var currentHome = 1
    var currentStation = 0
    
    while currentHome <= n {
        
        let startRange = stations[currentStation]-w < 1 ? 1 : stations[currentStation]-w
        let endRange = stations[currentStation]+w > n ? n : stations[currentStation]+w
        let currentRange = startRange...endRange
        
        if currentRange ~= currentHome { // 현재 기지국이 전파 범위에 포함 된다면
            currentHome = (endRange + 1) // 전파 범위 탈출
             
            if currentStation < stations.count - 1 { // 다음 기지국이 있다면
                currentStation += 1 // 다음 기지국 전파 범위 비교
            }
            
            // 다음 기지국이 없으면 무시
            
        } else { // 현재 기지국이 전파 범위에 포함 되지 않는 다면
            answer += 1
            currentHome += (2 * w + 1)
        }

    }
    
    return answer
}

---

Review

 

처음에 문제는 해결 했지만, 공간 / 시간복잡도를 고려하지 않았습니다. 시도를 하고 개선을 하면 된다고 생각 했기 때문입니다.

아래는 처음 작성 했던 코드입니다.
O(N * W) 의 복잡도가 나와 사실상 200,000,000 * 10,000 = 2조 번의 연산을 하기 때문에 효율성 테스트에서 떨어집니다.
또한 최악의 경우 2억 개의 원소가 있는 배열 메모리를 사용해야 해서 극한의 비효율적인 코드입니다.

// 처음 제출한 답안 (효율성 ❌)
func solution(_ n: Int, _ stations: [Int], _ w: Int) -> Int {
    var networks = Array(repeating: 0, count: n) // 전파가 터지는지 안터지는지 판별하는 배열
    var index = 0
    var answer = 0
    
    for station in stations { // O(N * W)
        let startPointIndex = (station - w - 1 > 0) ? station - w - 1: 0
        let endPointIndex = (station + w - 1 < n) ? station + w - 1 : n - 1
        
        for i in startPointIndex...endPointIndex {
            networks[i] = 1
        }
    }
    
    while index < n {  // O(N)
        if networks[index] == 1 {
            index += 1
        } else {
            index += (2 * w + 1)
            answer += 1
        }
    }
    
    return answer
}

물론 기지국을 설치하는 방법은 O(N)으로 해결할 수 있었습니다.

가장 큰 문제는 여기서 문제는, 기지국이 설치가 되어있는 위치를 효율적 이게 만드는 것이었습니다.

OMG..

---

개선하기

 

여기서 아예 다른 방법 ⭐️ 으로 풀어야겠다라고 생각했습니다.
저는 공간도 절약하고, 시간을 절약하는 방법을 고민 해봤습니다.

이제 문제 해결을 해봅니다.

효율성이 똥 같은 코드는 바로 아래 코드 입니다. 시간복잡도도 크고, 공간복잡도도 많이 잡아먹습니다.

for station in stations { // O(N * W)
    let startPointIndex = (station - w - 1 > 0) ? station - w - 1: 0
    let endPointIndex = (station + w - 1 < n) ? station + w - 1 : n - 1

    for i in startPointIndex...endPointIndex {
        networks[i] = 1
    }
}

이 코드는 현재 기지국이 설치되어 있어 전파되는 범위를 초기화하는 코드입니다.

공간복잡도를 줄이기 위해 (배열 메모리를 사용 X) 이제 완전히 다른 사고로 접근하였습니다.

생각의 결론은 다음과 같습니다.

index를 활용하여 집 하나하나 방문하면서
1. 해당 집에 전파가 터지는 범위면 전파가 터지는 범위 다음까지 이동을 해줍니다.
2. 전파가 터지지 않는다면 범위만큼 안테나를 세워주고, 전파가 터지는 범위 다음까지 이동을 시켜 줍니다.

쉽게 말해서, 반복문 하나로 해결할 수 있었습니다.

이 방법은 메모리를 사용하지 않고, 시간복잡도도 O(N)으로 해결 할 수 있습니다.

(엄밀히 말하면 투 포인터(Two Pointers) 알고리즘의 전형적인 형태는 아니지만, 유사한 방식으로 동작합니다.)
하나는 집을 이동하는 포인터, 하나는 전파 범위를 지정하는 포인터

import Foundation

func solution(_ n: Int, _ stations: [Int], _ w: Int) -> Int {
    var answer = 0
    var currentHome = 1
    var currentStation = 0
    
    while currentHome <= n {
        
        let startRange = stations[currentStation]-w
        let endRange = stations[currentStation]+w
        let currentRange = startRange...endRange
        
        if currentRange ~= currentHome { // 현재 기지국이 전파 범위에 포함 된다면
            currentHome = (endRange + 1) // 전파가 끝나는 다음 집으로 이동
             
            if currentStation < stations.count - 1 { // 다음 기지국이 있다면
                currentStation += 1 // 다음 기지국 전파 범위 비교
            }
            
            // 다음 기지국이 없으면 무시
            
        } else { // 현재 기지국이 전파 범위에 포함 되지 않는 다면
            answer += 1
            currentHome += (2 * w + 1)
        }

    }
    
    return answer
}

 

자 이제 코드를 이해해 봅니다.

우리에겐 예시 파라미터가 존재합니다. (문제에 나와 있습니다.)

n = 11 (집의 수)
stations = [4, 11] (현재 안테나가 존재하는 집)
w = 1 (전파가 되는 범위)

1. 1번 집은 전파 범위에 포함되지 않습니다. 전파되는 범위로 만들어 주고, currentHome 를 4번 집으로 이동시킵니다.
answer += 1

2. 4번 집은 전파가 잘됩니다. 전파가 되는 범위 다음으로 이동시켜줍니다. 즉 currentHome 를 6번으로 이동시킵니다.

3. 6번 집은 전파 범위에 포함되지 않습니다. 전파되는 범위로 만들어 주고, currentHome를 9번 집으로 이동시킵니다.
answer += 1

4. 9번 집은전파 범위에 포함되지 않습니다. 전파되는 범위로 만들어 주고, currentHome 를 12번 집으로 이동시킵니다.
answer += 1

5. currentHome 이 n 보다 커졌으니 프로그램을 종료합니다.

answer = 3

 

코드 수정후 효율성 테스트도 통과 할 수 있었습니다.

 

다른 의견이 있으시면 언제든지 말씀해 주세요. 감사합니다.