해시맵 (feat.백준 7785번)

1. 해시맵이란?

인덱스 대신에 Key값을 통해서 배열에 접근 할 수 있게 해주는 자료구조이다.

Key - Value 쌍으로 구성되어있으며 Key를 Hash Function을 통해서 인덱스화하고 이를 기반으로 값을 저장해준다.

 

만약 우리가 100만명의 유저의 전화번호 데이터를 가지는 테이블이 있다고 가정해보자. 이 100만명의 사람들중 특정 유저의전화번호 정보를 수정해야 하는 일이 발생한다면 이사람의 정보를 수정하기 위해서는 먼저 100만개의 테이블에서 내가 수정하고자 하는 유저의 정보가 테이블의 몇번째 인덱스에 있는지 부터 찾아야 할것이다. 

 

그러면 처음부터 끝까지 내가 원하는 유저를 찾을떄까지 탐색을 진행해야하고, 최악의 경우 100만번의 연산이 필요하게된다. 이는 굉장히 비효율적이고 오랜 시간이 걸리게 될것이다.

 

2. 해시맵 사용 이유

따라서 모든 테이블을 확인하는게 아니라 해시맵을 사용하여 유저의 이름 즉, key값을 인덱스로 변환하여 저장해두고 다시 접근할때도 해당 인덱스를 통해 값을 찾는다면 O(1) 시간만에 특정 유저의 정보에 접근할수 있다.

3. 예제

 

https://www.acmicpc.net/problem/7785

7785번: 회사에 있는 사람

위 문제는 특정 이름을 가진 사람의 출근정보가 입력으로 들어오게되고 현재 근무중인 사람의 이름을 출력하는 문제이다.

 

입력으로 10^6개의 입력이 들어오게되므로 일반적인 배열을 탐색하는 구조로 값을 참조하고 수정하는 연산을 수행한다면 O(n^2)의 시간이 나오게되어 시간초과로 통과를 할수 없는 문제이다.

 

따라서 해시맵을 통해 탐색연산시간을 O(1)로 줄여준다면 성공적으로 제한시간내에 문제를 풀 수 있다.

4. 풀이코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

map<string, bool> hashMap;


int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	string name, log;
	bool isWork;

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> name >> log;

		if (log == "enter")
			hashMap[name] = true;
		else
			hashMap[name] = false;
	}

	for (map<string, bool>::reverse_iterator riter = hashMap.rbegin(); riter != hashMap.rend(); riter++) {
		if(riter->second == true)
			cout << riter->first << "\n";
	}
	return 0;
}

모든 n만큼 for문을 돌면서 만약 enter가 들어오면 해당 사원의 이름을 해시맵의 인덱스로 하고 출근상태를 true로 추가, 만약 enter가 아니고 leave라면 해당 사원의 이름을 가진 인덱스의 값을 false로 변경해준다.

 

최종적으로 값이 true인 사원 즉, 출근은 했지만 아직 퇴근 로그가 찍히지 않은 사원의 이름을 출력해준다.