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

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

프로그래머스

 

2023.07.07 기준 Level 3

 

알고리즘 공부용으로 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

우선 주어진 N이 2억개까지 가능하기 때문에 이 N을 기준으로 반복문을 돌게 되면 시간초과가 발생할 확률이 높다.

따라서 직접 아파트들의 어레이를 만들어서 체크하는 아이디어는 배제했다.

 

여기서 힌트는 stations가 오름차순으로 정렬되어 주어진다는 것이다.

각 기지국이 정렬되어 있기 때문에 첫 번째 기지국부터 어디까지 커버가 가능한지 체크하면서 다음 기지국을 검사하면 될 것 같다는 생각이 들었다.

 

단, 한 기지국을 검사할 때 해당 기지국의 좌 우 커버 범위를 전부 검사하는 것이 아닌 기준 기지국의 좌측과 이전 기지국의 우측 커버 범위를 비교한다. (어차피 모든 stations를 다 탐색할 것이기 때문에 좌우를 한번에 검사할 필요가 없기 때문이다.)

 

만약 이전 기지국의 우측 커버 범위와 현재 기준 기지국의 좌측 커버 범위가 떨어져 있다면 해당 범위에 새로운 기지국이 필요한 것이다.

두 범위의 차를 구하여 기지국 설치가 필요한 아파트들의 개수를 구하고 한 기지국이 커버 가능한 범위인 2*w+1을 나누어서 새로 설치할 기지국의 개수를 구한다.

---

예시

1	2	3	4	5	6	7	8	9	10
	커버	기지국	커버					커버	기지국

w = 1 기준 위와 같은 상황이 주어진다면

stations = [3, 10] 이다.

우선 첫 번째 기지국인 3번에 위치한 기지국과 이전 기지국을 비교한다.

이 때, 이전 기지국이 없기 -w에 위치한 것으로 정한다.

이 사례에서는 -1인 것이다.

-1번 기지국의 우측 커버 범위는 0번까지이다.

3번 기지구의 좌측 커버 범위는 2번까지이다.

0과 2 사이에는 1개의 아파트가 남아 있다.

answer에 1 / (2*w+1)을 올림하여 더해준다.

 

두번째 기지국인 10번으로 이동한다.

이 때 이전 기지국은 3번 기지국이며 우측 커버 범위는 4번이다.

10번의 우측 커버범위는 9번까지이다.

4와 9 사이에는 4개의 아파트가 커버를 받지 못하고 있다. 

따라서 answer에 4(2*w+1)을 올림하여 더해준다.

 

결과적으로 answer = 3이 된다.

---

 

풀이

fileprivate func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var answer = 0
    
    func calculateStationsCntRequired(apartmentsCnt: Int) {
        if apartmentsCnt <= 0 { return }
        let newStationsCnt = ceil(Double(apartmentsCnt) / Double(2*w+1))
        answer += Int(newStationsCnt)
    }

    for i in 0..<stations.count {
        let station = stations[i]
        // 이전 스테이션과 비교해서 커버 가능한지 판단
        let prevStation = i == 0 ? -w : stations[i-1]
        
        let prevStationCoverRight = prevStation + w
        let currentStationCoverLeft = station - w
        
        
        // 이전 스테이션의 우측 커버 범위와 현재 스테이션의 좌측 커버 범위가 떨어져 있을 때 => 즉, 새 스테이션을 추가해야 하는 상황
        if prevStationCoverRight + 1 < currentStationCoverLeft {
            let targetApartmentsCnt = currentStationCoverLeft - (prevStationCoverRight + 1)
            calculateStationsCntRequired(apartmentsCnt: targetApartmentsCnt)
        }
        
        // 마지막 스테이션의 우측 부분 검사
        if i == stations.count - 1 {
            let lastStationCoverRight = station + w
            let targetApartmentsCnt = n - lastStationCoverRight
            calculateStationsCntRequired(apartmentsCnt: targetApartmentsCnt)
        }
    }

    return answer
}

마지막 스테이션의 경우는 우측 커버 범위에서 마지막 아파트까지의 남은 아파트들을 따로 계산해서 넣어줘야한다.

(반복문에서는 기지국의 좌측을 기준으로만 계산해서 마지막 스테이션은 우측을 검사받지 못하기 때문)

 

마무리

N이 2억인 것을 확인하고 N을 직접 이용하는 풀이법은 제외하는 스킬?이 필요했습니다.

Stations 배열이 정렬되어 있다는 것을 기반으로 이것을 순회하며 기준 기지국이 커버하는 범위와 이전 기지국이 커버하는 범위를 비교하고 커버 받지 못한 부분에 새 기지국 추가하는 방식을 떠올렸습니다.

시간 복잡도: O(n)