計算量を最適化して問題を解く必要がありますか？

1回目の提出の際は、時間計算量、空間計算量を考慮せず、Brute-force（総当たり）で解いてみることをおすすめします。それはBrute-forceで解く場合と最適化して解く場合で難易度が全く異なるからです。

まずは自分のチカラだけで解いてみよう

Recursionでは「Think For YourSelf」という方針を大切にしています。自分で考えて独自のソリューションが開発できるようになるためにも、まずは頑張って自分のチカラで解いてみましょう。

それでは有名なTwo Sumという問題をBrute-forceで解いた場合と、最適化して解く場合を例として考えてみましょう。

ID258 足して合計値
整数で構成される配列intArrとターゲットsumが与えられるので、配列内の2つの数字を足し合わせてtargetに一致するペアのインデックスを出力してください。

この問題をBrute-forceで解くことはとても簡単です。以下のように2つのfor文を入れ子で使い、それぞれの要素と残りの要素の合計がtargetに一致するかどうか全通りチェックすれば問題ありません。

function twoSum(intArr,sumInt){
    for (let i = 0; i < intArr.length; i++) {
        for (let j = i+1; j < intArr.length; j++) {
            if (intArr[i] + intArr[j] == sumInt) return [i,j];
        }
    }
    return [];
}

しかし、この問題を計算量を意識して解くとなれば、難易度はかなり上がります。配列の検索はO(n)なので、ルックアップの計算量が少ないハッシュマップを使って、インデックスと値の情報を保存します。その後、for文を使ってペアがハッシュマップ内に存在するかチェックしていきます。

function twoSum(intArr,sumInt){
    let hashmap = [];

    for (let i = 0; i < intArr.length; i++) {
        const curr = intArr[i];
        if(!(curr in hashmap)) hashmap[curr] = i;
    }

    for (let i = 0; i < intArr.length; i++) {
        const diff = sumInt - intArr[i];
        if (diff in hashmap && hashmap[diff] != i) {
            const j = hashmap[diff];
            return j > i ? [i, j] : [j, i];
        }
    }

    return [];
}

このようにコードは少し煩雑になり、問題としての難易度は上がりますが、計算量は大幅に削減することができます。コードの計算量を削減するにはアルゴリズムやデータ構造の知識が必要になります。

高い目標を持つ方にはおすすめ

Brute-Forceで解く場合と最適化して解く場合は難易度が大幅に異なるため、コーディング面接ではアルゴリズムやデータ構造の知識が必要になることがあります。特に将来レベルの高い開発者や、有名企業でソフトウェアエンジニアとして勤務したい場合は計算量を意識して問題を解いてみましょう。Recursionの模範解答を上手く活用して学習を進めても良いかもしれません。