[Algorithm] MinMaxDivision

[hwangJi-dev]

💬 문제

https://app.codility.com/programmers/lessons/14-binary_search_algorithm/min_max_division/

💬 Idea

• 이분탐색 알고리즘을 사용해서 푸는 문제였다. 그러나 이분탐색 알고리즘을 응용해 해당 문제에 적용시키는 것이 많이 어려웠다. 앞으로 더 공부해야겠다!

💬 풀이

public func solution(K : Int, M : Int, A : inout [Int]) -> Int {
    var low = A.max()!
    var high = A.reduce(0, +)
    
    if K == 1 { return high }
    if K >= A.count { return low }
    
    while low <= high {
        let mid = (low + high) / 2
        
        if isValid(A: A, maxBlockCount: K, maxBlockSize: mid) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    return low
}

func isValid(A: [Int], maxBlockCount: Int, maxBlockSize: Int) -> Bool {
    var blockSum = 0
    var blockCount = 0
    
    for a in A {
        if blockSum + a > maxBlockSize {
            blockSum = a
            blockCount += 1
        } else {
            blockSum += a
        }
        
        if blockCount >= maxBlockCount {
            return false
        }
    }
    
    return true
}

**소요시간** : 73분

시간 복잡도 : O(Nlog(N+M))*

평가표 : https://app.codility.com/demo/results/trainingW3HGHY-P47/