해시맵(Hash Map)으로 푸는 자물쇠와 열쇠(Lock & Key) 매칭 문제

서로 다른 자물쇠(lock)들의 목록과 열쇠(key)들의 목록이 주어졌을 때, 각 열쇠가 어떤 자물쇠와 짝이 되는지 찾아 올바르게 매칭하는 것이 이 문제의 목표입니다. 정렬되지 않은 두 목록에서 일대일 대응 관계를 효율적으로 찾아내야 하는 상황이죠.

이 문제를 해결하는 가장 효율적인 방법 중 하나는 해시맵(Hash Map)을 활용하는 것입니다. 먼저 모든 자물쇠를 순회하면서 해시맵을 생성하고, 그다음 각 열쇠를 해시맵에서 조회합니다. 열쇠가 해시맵에 존재하면 유효한 열쇠로 판정하여 해당 위치의 자물쇠와 매칭합니다.

입력과 출력 예시

입력:
자물쇠 목록과 열쇠 목록
lock = { ),@,*,^,(,%,!,$,&,#}
key = { !, (, #, %, ), ^, &, *, $, @ }

출력:
자물쇠와 열쇠 매칭 후:
Locks: ! ( # % ) ^ & * $ @
Keys: ! ( # % ) ^ & * $ @

알고리즘 동작 원리

핵심 아이디어는 단순합니다. 자물쇠 배열을 한 번 순회하며 hashmap[lock[i]] = i 형태로 인덱스를 저장한 뒤, 열쇠 배열을 순회하면서 해당 열쇠가 해시맵에 있는지 확인합니다. 존재한다면 그 열쇠를 같은 위치의 자물쇠에 할당하면 됩니다.

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

C++ 구현 예제

아래는 C++의 map 컨테이너를 사용해 실제로 구현한 코드입니다. STL의 map은 내부적으로 균형 이진 탐색 트리를 사용하지만, unordered_map으로 바꾸면 진정한 의미의 해시 기반 O(1) 조회도 가능합니다.

#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: ! ( # % ) ^ & * $ @

시간 복잡도 분석

이 알고리즘의 시간 복잡도를 살펴보면 다음과 같습니다.

해시맵 생성 단계: 자물쇠 n개를 모두 삽입하므로 O(n)
매칭 단계: 각 열쇠에 대해 해시맵 조회를 수행하므로 평균 O(n)
전체 시간 복잡도: O(n) — 해시맵 조회가 평균 O(1)이라는 점을 활용

만약 해시맵 없이 이중 반복문으로 모든 자물쇠-열쇠 조합을 비교한다면 O(n²)이 걸리지만, 해시맵을 사용하면 선형 시간에 문제를 해결할 수 있습니다. 공간 복잡도는 해시맵 저장을 위해 추가로 O(n)이 필요합니다.