ハッシュマップで解く「ロックとキー」マッチング問題 ― C++実装付きでわかりやすく解説

異なるロックのリストと、それとは別にキーのリストが与えられます。この課題の目的は、与えられたリストの中から正しく対応するロックとキーの組み合わせを見つけ出し、該当するキーを対応するロックに割り当てることです。

本記事で紹介するアプローチでは、まずすべてのロックを走査してハッシュマップを作成します。その後、各キーをハッシュマップ内で検索し、一致するものが見つかった場合に、そのキーを有効なキーとしてマークしてロックに割り当てます。ハッシュマップを利用することで、全件を総当たりで比較する方法(計算量 O(n²))と比べ、はるかに効率的な O(n) での解決が可能になります。

入力と出力

入力:
ロックとキーのリスト。
lock = { ),@,*,^,(,%,!,$,&,# }
key  = { !,(,#,%,),^,&,*, $,@ }

出力:
ロックとキーの照合後:
Locks: ! ( # % ) ^ & * $ @
Keys:  ! ( # % ) ^ & * $ @

アルゴリズム

lockAndKeyProblem(lock, key, n)

入力: ロックのリスト、キーのリスト、要素数 n。

出力: どのキーがどのロックに対応するかを求めます。

Begin
    define hashmap
    for i in range (0 to n-1), do
        hashmap[lock[i]] := i   //ロックの情報をハッシュマップに登録
    done

    for i in range (0 to n-1), do
        if key[i] is found in the hashmap, then
            lock[i] = key[i]    //対応するキーをロックに割り当て
    done
End

処理の流れ

1. 各ロックを走査し、「ロックの文字 → インデックス」の対応関係をハッシュマップに登録します。
2. 次に各キーについて、ハッシュマップ内に同じ文字が存在するかを確認します。
3. 存在していれば、その位置のロックを対応するキーで置き換えます。これにより、ロックとキーが同じ順序で並んだ状態になります。

C++による実装例

#include<iostream>
#include<map>
using namespace std;

void show(char array[], int n) {
    for(int i = 0; i<n; i++)
        cout << array[i] << " ";
}

void lockAndKeyProblem(char lock[], char key[], int n) {
    map<char, int> hashMap;
    for(int i = 0; i<n; i++)
        hashMap[lock[i]] = i;          //ロック用のハッシュマップを作成

    for(int i = 0; i<n; i++)           //各キーを順に照合
        if(hashMap.find(key[i]) != hashMap.end()) {
            lock[i] = key[i];          //一致したキーをロックに割り当て
        }
}

int main() {
    char lock[] = {')','@','*','^','(','%','!','$','&','#'};
    char key[]  = {'!','(','#','%',')','^','&','*','$','@'};
    int n = 10;
    lockAndKeyProblem(lock, key, n);
    cout << "After matching Locks and Keys:"<<endl;
    cout << "Locks: "; show(lock, n); cout << endl;
    cout << "Keys: ";  show(key, n);  cout << endl;
}

実行結果

After matching Locks and Keys:
Locks: ! ( # % ) ^ & * $ @
Keys:  ! ( # % ) ^ & * $ @

計算量

時間計算量: O(n) ― ロックの登録に n 回、キーの検索に n 回の操作が必要ですが、ハッシュマップによる検索は平均 O(1) で行えるため全体で線形時間に収まります。
空間計算量: O(n) ― ロックの分だけハッシュマップにエントリを保持するため、追加のメモリが必要です。

このように、ハッシュマップを活用することで、ロックとキーのマッチング問題をシンプルかつ高速に解くことができます。要素数が多いデータセットでも実用的に動作する点が大きなメリットです。