[Swift][이분 탐색] 백준 2110번 (공유기 설치)

요구능력

이분탐색(upperBound)

 

문제풀이

mid의 경우 공유기가 들어갈 수 있는 집사이의 간격으로 기준을 잡았다.

집들의 거리가 저장된 배열을 가지고 집들끼리의 거리를 비교해서 인접한집끼리 거리가 mid보다 크거나 같을경우 공유기 설치가 가능하다.

 

후기

이분탐색은 기준을 잘 세우자..

 

코드

import Foundation
let nc = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nc[0]
let c = nc[1]

var arr = [Int]()
for _ in 0..<n{
    arr.append(Int(String(readLine()!))!)
}
arr.sort()

let maxArr = arr[n - 1]
let minArr = arr[0]
var start = 1
var end = maxArr - minArr
var result = 0

while start <= end{
    var count = 1 //설치 할 수 있는 공유기 수
    let mid = (start + end) / 2
    var prevHome = arr[0]
    for i in 1..<n{
        let currentHome = arr[i]
        if currentHome - prevHome >= mid{ //현재구한간격(mid)보다 크거나 같으면 공유기 설치 가능
            count += 1
            prevHome = currentHome
        }
    }
    
    if count < c{
        end = mid - 1
    }else{
        start = mid + 1
    }
}
print(start - 1)