최소값 조합 찾기

MinSumCombination.scala

object MinSumCombination {

  def findMin(nums: Array[Int]): Int = {
    val result = tryCombinations(nums, 0)
    if (result < Int.MaxValue) result else -1
  }

 private def tryCombinations(nums: Array[Int], fixPos:Int): Int = {
    //println((nums).mkString(","))
    if(fixPos >= nums.length - 1) Int.MaxValue
    
    val minValue = minSumOfTwoGroups(nums)
    (fixPos+1 until nums.length).fold(minValue)(
      (curMin, idx) => Math.min(curMin, tryCombinations(
          (nums.take(fixPos) :+ nums(idx)) ++ nums.slice(fixPos, idx) ++ nums.drop(idx + 1), fixPos + 1)))
  }


  private def minSumOfTwoGroups(nums: Array[Int]): Int = {
    (1 until nums.length).fold(Int.MaxValue)(
      (min, idx) =>
        Math.min(min, {
          val groups = nums.splitAt(idx)
          sum(groups._1, groups._2)
        }))
  }

  def sum(a: Array[Int], b: Array[Int]) = a match {
    case Array(h, _*) if h > 0 => b match {
      case Array(h, _*) if h > 0 => intVal(a) + intVal(b) // println("\t" + a.mkString + " + " + b.mkString + " = " + (sum(a) + sum(b)))
      case _ => Int.MaxValue
    }
    case _ => Int.MaxValue
  }
  
  def intVal(nums: Array[Int]): Int = (0 /: nums)((a, b) => (a*10) + b)
}

MinSumCombinationSpec.scala

import org.junit.runner.RunWith

import org.scalatest.FunSuite
import org.scalatest.junit.JUnitRunner

import MinSumCombination._

@RunWith(classOf[JUnitRunner])
class MinSumCombinationSpec extends FunSuite{
  
  test("다양한 조합의 두 그룹의 합 중 최소값을 반환한다.") {
	  assert(findMin(Array(1, 2, 4, 7, 9)) == 176)
  }
  
  test("중복된 숫자도 허용") {
	  assert(findMin(Array(1, 2, 3, 1, 2, 3)) == 246)
	  assert(findMin(Array(1, 2, 3, 4, 5, 6, 7)) == 1603)
    
  }
  
  test("조합 중 숫자가 앞에 0이면 무효화") {
	  assert(findMin(Array(0, 1, 2, 3, 0, 1, 2, 3, 4)) == 11257)
  }
  
  test("가능한 조합이 없을 때에는 -1 반환") {
	    assert(findMin(Array(0, 0, 1)) == -1)
  }
}