ปัญหาล็อกและกุญแจ (Lock & Key Problem) ด้วย Hash Map

บทนำ

กำหนดรายการล็อก (Locks) ที่แตกต่างกัน และรายการกุญแจ (Keys) อีกชุดหนึ่ง ภารกิจคือหาคู่ที่ตรงกันของล็อกและกุญแจจากรายการที่กำหนด และกำหนดกุญแจนั้นกับล็อกเมื่อตรงกัน

ในแนวทางนี้ เราจะเดินทาง (Traverse) ผ่านล็อกทั้งหมดและสร้าง Hash Map หลังจากนั้น แต่ละกุญแจจะถูกค้นหาใน Hash Map เมื่อกุญแจตรงกัน แล้วจะถูกทำเครื่องหมายว่าเป็นกุญแจที่ถูกต้องและกำหนดกับล็อก

อินพุตและเอาต์พุต

Input: รายการล็อกและกุญแจ
lock = { ),@,*,^,(,%, !,$,&,#}
key = { !, (, #, %, ), ^, &, *, $, @ }
Output: หลังจับคู่ Locks และ Keys:
Locks: ! ( # % ) ^ & * $ @
Keys:  ! ( # % ) ^ & * $ @

อัลกอริทึม

lockAndKeyProblem(lock, key, n)
Input: รายการล็อก, รายการกุญแจ, n
Output: หาว่ากุญแจไหนสำหรับล็อกไหน

Begin
    กำหนด hashmap
    for i ในช่วง (0 ถึง n-1), do
        hashmap[lock[i]] := i  // ตั้งค่า hashmap สำหรับล็อก
    done
    for i ในช่วง (0 ถึง n-1), do
        if key[i] พบใน hashmap, then
            lock[i] = key[i]
    done
End

ตัวอย่างโค้ด (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 hashMap;
    for (int i = 0; i < n; i++)
        hashMap[lock[i]] = i;  // hash map สำหรับล็อก
    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: ! ( # % ) ^ & * $ @