• 2
    Like
  • 3
    Comment
More than 1 year has passed since last update.

もっとエンジニア力つけたい!というわけで、ペーペーなプログラマを脱するべく、毎週Qiitaに投稿しようと思います。

で、今、社内でアルゴリズムの勉強会してるので、まずはそのコードを晒していこうと思います。
今回のお題はFenceRepair
フェンスの修理を最小コストで行なえというやつです。

修理のために板を分割するのですけど、分割すると、分割前の板の長さのコストがかかります。
30の板を、5、5、20の長さに分割するとします。
まず、5、25で分割すると、30のコスト。
25をさらに5と20で分割すると、25のコスト、合わせて55のコストが必要となります。

インプットは、分割後の板の長さです(上記の例だと、5、5、20)。
元の板の長さは、分割後の合計の長さと一致します。
この時のコストを最小にするアルゴリズムを考えよ!というわけです。

で、できたのがコチラ。

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でいうと、ヒープキューアルゴリズムとかでしょうか。

次は、もっとカッコよく・・・!

  • Linked from these articles
  • Linked from 柵を修理