Hash-map을 사용한 Lock &Key 문제

다른 잠금 목록과 다른 키 목록이 제공됩니다. 우리의 임무는 주어진 목록에서 자물쇠와 열쇠의 정확한 일치를 찾고 그것이 정확할 때 자물쇠와 함께 그 열쇠를 할당하는 것입니다.

이 접근 방식에서 우리는 모든 잠금을 탐색하고 해시 맵을 생성한 후 해시 맵에서 각 키를 검색합니다. 키가 일치하면 유효한 키로 표시되고 잠금이 할당됩니다.

입력 및 출력

Input:
The lists of locks and keys.
lock = { ),@,*,^,(,%, !,$,&,#}
key = { !, (, #, %, ), ^, &, *, $, @ }
Output:
After matching Locks and Keys:
Locks: ! ( # % ) ^ & * $ @
Keys: ! ( # % ) ^ & * $ @

알고리즘

lockAndKeyProblem(lock, key, n)

입력: 자물쇠 목록, 키 목록, n.

출력: 어떤 열쇠가 어떤 자물쇠를 위한 것인지 찾으십시오.

Begin
   define hashmap
   for i in range (0 to n-1), do
      hashmap[lock[i]] := i  //set hashmap for locks
   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

예시

#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;           //hash map for locks

   for(int i = 0; i<n; i++) //for each keys for each lock
      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: ! ( # % ) ^ & * $ @