もっとエンジニア力つけたい！というわけで、ペーペーなプログラマを脱するべく、毎週Qiitaに投稿しようと思います。
で、今、社内でアルゴリズムの勉強会してるので、まずはそのコードを晒していこうと思います。
今回のお題はFenceRepair。
フェンスの修理を最小コストで行なえというやつです。
修理のために板を分割するのですけど、分割すると、分割前の板の長さのコストがかかります。
３０の板を、５、５、２０の長さに分割するとします。
まず、５、２５で分割すると、３０のコスト。
２５をさらに５と２０で分割すると、２５のコスト、合わせて５５のコストが必要となります。
インプットは、分割後の板の長さです（上記の例だと、５、５、２０）。
元の板の長さは、分割後の合計の長さと一致します。
この時のコストを最小にするアルゴリズムを考えよ！というわけです。
で、できたのがコチラ。
FenceRepair.php
class FenceRepair
{
public static function calc($boardsLength)
{
$cost = 0;
asort($boardsLength);
while (count($boardsLength) > 1) {
$firstBoard = array_shift($boardsLength);
$secondBoard = array_shift($boardsLength);
$cost += $newBoard = $firstBoard + $secondBoard;
$boardsLength = FenceRepair::insertNumToArrayThroughAsort($newBoard, $boardsLength);
}
return $cost;
}
private static function insertNumToArrayThroughAsort($num, $array)
{
foreach ($array as $key => $value) {
if ($value >= $num) {
array_splice($array, $key, 0, $num);
return $array;
}
}
array_push($array, $num);
return $array;
}
}
切るたびに切る前の板の長さのコストがかかるので、切るときは、切った後の板の長さが、最も小さいものを選ぶ、ということを、逆算したような処理になってます。
insertNumToArrayThroughAsort()で毎回ソートしてるので、ちょっと無駄な処理をしてます。
heapSortを使えば、もうちょっとカッコよくなるらしいです。
Pythonでいうと、ヒープキューアルゴリズムとかでしょうか。
次は、もっとカッコよく・・・！