이진 탐색 - 떡볶이 떡 만들기(Swift)

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다.

 

풀이 코드

// 입력 조건
// 4 6
// 19 15 10 17

import Foundation

let input = readLine()!.split(separator: " ").map({Int(String($0))!})
var heightArr = readLine()!.split(separator: " ").map({Int(String($0))!})

let n = input[0]
let target = input[1]

var start = 0
var end = heightArr.max()!

while true {
    
    if start > end {
        print("X")
        break
    }
    
    let mid = Int(floor((Double(start) + Double(end)) / 2))
    var result = 0
    
    for i in 0..<n {
        if heightArr[i] > mid {
            result += heightArr[i] - mid
        }
    }
    
    if result == target {
        print(start)
        break
    } else if result > target {
        start = mid + 1
    } else {
        end = mid - 1
    }
}

// 15