[C++ 백준 풀이] 17219번 : 비밀번호 찾기 (해시맵 Hashmap 기초)

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 17219번 : 비밀번호 찾기 문제에 대한 풀이와 해시맵 Hashmap 기초를 다룹니다.

 

아무래도 다른 문제들을 풀 때 지나가는 식으로 풀이하기보다는 보충 설명을 위한 참조 링크라도 달아두기 위해서, 기본적으로 해시맵에 대한 개념을 짚고 넘어가야 할 것 같아 가장 기본적인 해쉬맵 문제를 예시로 풀이를 해보겠습니다.

 

 

17219번 : 비밀번호 찾기

 

N개의 아이디와 비밀번호에 대한 입력이 주어지고, 그 다음 M개의 아이디가 입력되었을 때 해당하는 비밀번호를 찾아 출력하는 문제입니다.

얼핏 보았을 때는 굉장히 간단해보이는 문제이지만 10만개의 입력이 주어지고 이들을 각각 탐색하기 위해서는 10만개로 이루어진 배열을 2중으로 반복해야하기 때문에 5초라는 이 문제의 제한 시간 안에 해결이 불가능합니다.

 

따라서 이 문제를 해결하는 방법은 크게 2가지가 있습니다.

1. 문자열을 이용해 정렬에 대한 기준을 만들어 정렬하고, 이진 탐색 수행

2. 해시맵 (Hashmap)

 

1번은 문자열을 정렬하는 과정과 이진 탐색에 대한 코드까지 작성해야 하기 때문에 굉장히 귀찮은데요, 이러한 문제를 해결할 수 있는 것이 해시맵입니다.

해시맵은 어떤 key값이 주어지면 이 key값에 대한 연산을 통해 즉시 value에 도달할 수 있으므로 정렬이나 탐색이 아예 필요가 없습니다.

(간단히 어떤 계산식을 정의하고, 해당 계산 값에 대한 소수에 대한 나머지를 이용해 value에 도달한다고 생각하면 됩니다.)

 

해시맵을 순수하게 100% 구현하기 위해서는 계산식과 테이블, 그리고 테이블의 같은 value에 값들이 중복되는 것까지 고려를 해야하기 때문에 생각보다 복잡합니다.

그래서 웬만하면 구현하려고 했는데 결국 그냥 C++의 map 헤더파일을 사용했습니다.

 

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

int main() {
    int n, m;
    string id, pw;
    map <string, string> account;
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> id >> pw;
        account[id] = pw;
    }
    for(int i=0; i<m; i++) {
        cin >> id;
        cout << account[id] << '\n';
    }
}

 

사용법은 위와 같이 map<data type, data type>으로 선언하고, 값에 도달할 때는 변수명[key] = value로 접근하시면 됩니다.

이론적으로 배울 수 있는 table 생성과 식에 대한 모든 함수들이 헤더파일에 이미 구현이 되어있어서 이를 사용만 하면 되는 것입니다.

 

 

위의 코드로 제출하면 5000ms라는 제한 시간에 대해 거의 아슬아슬하게 100% 정답 인정을 받을 수 있습니다.