C++で2つのリストの最小インデックス合計を求める方法

友人であるアマルとビマルが、夕食のためのレストランを選ぼうとしています。二人とも、文字列として表されたお気に入りのレストランのリストを持っており、その中からリストインデックスの合計が最小となる共通のレストランを見つけたいと考えています。もし複数の候補が同点になった場合は、順序を問わずすべての候補を返します。

例えば、入力が ["ABC","PQR","MNO","XYZ"] と ["TUV","GHI","KLM","ABC"] の場合、出力は ["ABC"] となります。

解法のアプローチ

この問題は、共通する要素を「インデックスの合計」をキーとしてマップに記録していくことで解決できます。以下の手順に従いましょう。

• マップ mp を定義する（キー：インデックスの合計、値：レストラン名のベクター）
• least を INT_MAX（無限大相当）で初期化する
• i を 0 から l1 のサイズ未満まで増やしながらループする
  • j を 0 から l2 のサイズ未満まで増やしながらループする
    • l1[i] と l2[j] が一致した場合、mp[i + j] の末尾に l1[i] を追加する
• 結果用の配列 res を定義する
• it をマップの先頭要素とする
• res に it の値を代入する
• res を返す

C++の std::map はキーが自動的に昇順ソートされるため、マップの先頭要素には最小のインデックス合計に対応するエントリが格納されています。これにより、同点の候補もすべてまとめて取得できます。

実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<string> findRestaurant(vector<string>& l1, vector<string>& l2) {
        map<int, vector<string> > mp;
        int least = INT_MAX;
        for (int i = 0; i < l1.size(); i++)
            for (int j = 0; j < l2.size(); j++)
                if (l1[i] == l2[j])
                    mp[i + j].push_back(l1[i]);
        vector<string> res;
        auto it = mp.begin();
        res = it->second;
        return res;
    }
};
main(){
    Solution ob;
    vector<string> v = {"ABC","PQR","MNO","XYZ"}, v1 = {"TUV","GHI","KLM","ABC"};
    print_vector(ob.findRestaurant(v, v1));
}

入力

{"ABC","PQR","MNO","XYZ"}, {"TUV","GHI","KLM","ABC"}

出力

[ABC]

計算量について

このアルゴリズムでは、2つのリストの全組み合わせを比較するため、時間計算量は O(n × m)（n、m はそれぞれのリストの長さ）となります。リストのサイズが小さい場合は十分実用的ですが、より大きなデータセットに対しては、ハッシュマップ（unordered_map）を活用して片方のリストを事前に登録しておくことで、効率を改善することも可能です。