백준[2110] 공유기 설치 (Swift)

문제를 읽었을 때 문제가 이해가 되지 않아서 3번 정도 읽고, 머리로는 이해했지만 이게 이진탐색이라고.?라는 생각이 곧바로 들었다.

 

이전 실버 난이도 문제에서는 이진탐색을 이용하겠네 라는 생각이 들고 그 생각을 가지고 살짝 응용한다면 골드 문제부터는 이진탐색을 적용해야 하는 mid, start, end 기준을 스스로 생각하여 정해야 풀 수 있는 문제들인 것 같다.

어렵..

 

mid 기준만 정하는 게 가장 큰 난관이다.ㅠㅠ

 

import Foundation

func findMaxOfMinimum(arr: [Int], start: Int, end: Int, c: Int) -> Int{
    var start = start
    var end = end
    
    while start <= end{
        var count = 1
        let mid = (start + end)/2
        var prevHouse = arr[0]
        
        for i in 1..<arr.count{
            let curHouse = arr[i]
            if curHouse - prevHouse >= mid{
                count += 1
                prevHouse = curHouse
            }
        }
        
        if count < c {
            end = mid - 1
        }
        else{
            start = mid + 1
        }
    }
    return start - 1
}

func installNode(){
    
    let input = readLine()!.split(separator: " ").map({Int($0)!})
    let n = input[0]
    let c = input[1]
    var arrN = [Int]()
    
    for _ in 0..<n {
        arrN.append(Int(readLine()!)!)
    }
    
    arrN.sort()
    
    print(findMaxOfMinimum(arr: arrN, start: 1, end: arrN[n-1] - arrN[0], c: c))    
}