[프로그래머스/Lv.3] Swift - 기지국 설치

2025.03.19 기준 Level 3
https://school.programmers.co.kr/learn/courses/30/lessons/12979

알고리즘

그리디

문제 요약

- 전파 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있다.

영향력이 1인 기지국이 4번과 11번 아파트에 설치되었을 때, 1, 2, 6, 7, 8, 9는 전파가 전달되지 않는다.

1, 7, 9번 아파트에 추가로 기지국을 설치하면 모든 아파트에 전파가 전달된다.

모든 아파트에 전파를 전달하기 위해 증설해야할 기지국의 최솟값을 return

 

제약 조건

N: Int, 아파트의 개수

stations: [Int], 현재 기지국이 설치된 아파트의 번호

W: Int, 전파의 도달거리

• N <= 200,000,000 (2억 이하의 자연수)
• stations.count <= 10,000이하의 자연수
• stations는 오름차순 정렬되어 있고, 배열에 담긴 수는 N보다 같거나 작은 자연수
• W <= 10,000이하의 자연수

입출력 예

N	stations	W	answer
11	[4, 11]	1	3
16	[9]	2	3

 

아이디어

N의 크기가 최대 2억이기 때문에 배열을 생성하거나 하나씩 확인하는 것은 메모리초과 또는 시간초과가 발생할 것이라 생각함.

설치된 기지국을 기준으로 구간을 정해, 구간마다 기지국을 몇 개 더 설치해야하는지 확인

 

 

예제 1)

4, 11번에 기지국이 설치되었을 때 양쪽으로 1칸씩은 전파가 전달된다.

 

1. 구간 별 최소 기지국 설치 개수 확인

start: 이전 기지국 범위 이후

end: 현재 기지국 범위 이전

 

(a) 전파를 받지 않는 아파트 개수: end - start + 1

(b) 기지국 하나 당 영향 범위: W + 2

 

최소 설치해야하는 기지국 개수 = (a / b) + (a % b)

 

한 구간을 확인하면 start를 현재 기지국의 영향 범위 이후로 업데이트 해준다.

start = stations[i] + w + 1

 

2. 마지막 기지국 설치 범위 이후 확인

start == n인 경우 마지막 한 아파트가 전파를 전달받지 못한다는 뜻이므로 포함해주어야함.

 

풀이

// 그리디

import Foundation

func solution(_ n:Int, _ stations:[Int], _ w:Int) -> Int{
    var answer = 0

    let area = w + 1                                                // 설치 기지국의 한 쪽 영향력
    var start = 1
    for i in 0..<stations.count {
        let end = stations[i] - area                                // 기지국 영향력 왼쪽 부분
        answer += (end - start + 1) / (area + w)                    // 범위 / 한 기지국의 영향 범위
        if (end - start + 1) % (area + w) > 0 { answer += 1 }       // 범위 % 한 기지국의 영향 범위
        
        start = stations[i] + area                                  // 기지국 영향력 오른쪽 부분
    }
    
    // 마지막 기지국의 전달 영역이 아파트의 끝이 아닌 경우, start == n인 부분도 한 아파트가 남은 경우로 포함되어야 함.
    if start <= n {
        answer += (n - start + 1) / (area + w)
        if (n - start + 1) % (area + w) > 0 { answer += 1 }
    }
    
    return answer
}

 

 

다른 사람의 풀이

- 굳이 pop을 하지 않고 개수만 세어도 됨.

import Foundation

func solution(_ a:[Int], _ b:[Int]) -> Int {

    let sA = a.sorted()
    let sB = b.sorted()
    var index = 0

    for e in sB {
        if e > sA[index] {
            index += 1
        }
    }

    return index
}