BOJ-2110 공유기 설치 Swift

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

내가 푼 풀이

- 집의 좌표들을 오름차순으로 정렬하여 첫번째 집부터 차례대로 공유기를 설치하여 C만큼 설치했을때 공유기 거리의 최댓값으로 구해보자

- 이분탐색을 이용하였는데, 집의 좌표 사이의 거리들을 탐색하였다.

- 거리의 최소값은 집과 공유기의 갯수가 같으면 집집마다 설치하면 되므로 0이 되고, 거리의 최대값은 첫번째 집과 마지막번째 집사이의 거리가 된다.

- 이 거리를 공유기 설치 거리로 생각하고, 중간값부터 공유기를 설치해보고, 설치 개수가 C보다 같거나 많이 설치가 됬다면 거리를 좀 더 늘리고, C보다 적게 설치됬다면 설치거리를 줄여서 다시 설치하는 방향으로 한다.

 

import Foundation
// 입력받기
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0]
let C = input[1]
var arr = [Int]()
for i in 0..<N {
    arr.append(Int(readLine()!)!)
}
// 집좌표 오름차순 정렬
arr.sort(by: <)
// 집과 집사이의 공유기 설치거리 최솟값과 최댓값
// 최솟값은 집집마다 공유기 설치한다면 0, 최댓값은 정렬된 집좌표에서 첫번째집과 마지막번째 집사이의 거리가된다.
var startIndex = 0
var endIndex = arr[arr.endIndex - 1] - 0
var result = 0  // 결과를 저장할 변수

// 이분탐색
while startIndex <= endIndex {
    var count = 1
    var house = arr[0]
    let midIndex = (endIndex + startIndex) / 2
    // 첫번째 집부터 공유기를 설치해보고, 다음집까지 설치거리가 닿는다면 패스
    // 닿지 않으면 공유기를 새로 설치해야하므로 count ++ 하고, 기준이 되는 집 갱신한다.
    for i in 0..<N {
        let nextHouse = arr[i]
        if midIndex <= nextHouse - house {
            count += 1
            house = nextHouse
        }
    }
    // 공유기가 더 많이 설치가 됬다면, 설치거리가 짧아서 많은 집들에 설치가된것으로, 설치거리를 늘린다.
    // 공유기가 더 적게 설치가 됬다면, 설치거리가 길어서 한 집이 많은 집을 커버했다. 설치거리를 줄인다.
    // 이렇게 반복하면 설치거리가 최대가 될때까지 반복이 된다.
    if count >= C {
        result = midIndex
        startIndex = midIndex + 1
    } else {
        endIndex = midIndex - 1
    }
}

print(result)