コーディング面接対策サイトCodilityの練習問題を解いてみた(MinMaxDivision)

問題

配列AをK個に分割し、それぞれ分割したブロックの和を求める。 すべての配列の要素は5以下。

A = [2, 1, 5, 1, 2, 2, 2], K = 3, M = 5 なら

[2, 1, 5, 1, 2, 2, 2], , なら、分割したブロックの和の最大値 15; [2], [1, 5, 1, 2], [2, 2] なら、分割したブロックの和の最大値 9; [2, 1, 5], [], [1, 2, 2, 2] なら、分割したブロックの和の最大値 8; [2, 1], [5, 1], [2, 2, 2] なら、分割したブロックの和の最大値 6.

それぞれのパターンで算出した分割したブロックの和の最大値の中で、最小値を求めることがgoal。

Codility

回答

K == 1 なら各要素の総和(high)に K == 配列の長さなら、各要素の中で最大のもの(low)が答えに それ以外の場合なら、lowとhighの間に答えがあるはずなので、BinarySearchで、ちょっとずつ計算する

#A = [2,1,5,1,2,2,2]

def solution(k, m, a)
  if k == 1
    return a.inject(0) {|sum, x| sum + x }
  elsif k == a.length
    return a.max
  else
    # use binary search
    low = a.max
    high = a.inject(0) {|sum, x| sum + x }

    while (low <= high) do
      mid = (low + high) / 2
      p "mid = #{mid}"
      if check(a, k, mid)
        high = mid - 1
      else
        low = mid + 1
      end
    end
    return low
  end
end

def check(a, k, mid)
  sum = 0
  blocks = 0

  a.each {|e|
    if ( (sum + e) > mid )
      sum = e
      blocks += 1
      return false if blocks >= k
    else
      sum += e
    end
    #puts "sum = #{sum}, blocks = #{blocks}, k = #{k}, mid = #{mid} "
  }
  return true
end

p solution(3,5,A)