Hash(2) : unordered multimap

유리·2021년 4월 17일

자료구조

목록 보기

1/1

unordered multimap

특징 : 같은 인덱스값에 대해, 여러값을 저장 가능
-> 여러 값을 연결리스트의 노드 형태로 저장
사용법 : unordered map이랑은 값을 넣는 방법이 다름.
-> insert 메소드 이용
-> umm.insert({"ABC", 1});
그냥 hash 보다 사용이 불편하지만, 하나의 인덱스에 대해 여러값을 저장할 수 있다는 장점때문에 종종 쓰임.

코드로 unordered multimap 익히기

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_multimap<string, int> umm; // multimap

int main() {
	
	//umm은 배열형태로 삽입X, insert로 삽입
	umm.insert({ "ABC", 17 });
	umm.insert({ "ABC", 26 });
	umm.insert({ "ABC", 72 });


	// unordered_multimap 출력방법 -> 외우기!!
	auto mi = umm.equal_range("ABC");
	for (auto i = mi.first; i != mi.second; ++i) {
		cout << i->second << " "; // .second랑 ->second랑 다름
	}

	// 출력결과 : 17 26 72

	return 0;
}

(.second랑 ->second의 차이, equal_range 는 추가적으로 공부 필요)

unordered multimap 예제 : 자동완성 기능

문제 : 단어의 앞글자 (1개/2개/3개 중 하나)를 입력하면, 그 글자에 맞는 단어 검색 결과를 전부 출력하기
아이디어 : second값을 출력하는 것이므로, for문을 돌려서 단어의 1,2,3번째 글자들을 다 string으로 키값으로 넣어주자

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

unordered_multimap<string, string> umm;

void init() {
	string arr[6] = {
		"ABA",
		"TABC",
		"ARK",
		"BTS",
		"AGK",
		"ARBTC"
	};

	for (int i = 0; i < 6; i++) {
		umm.insert({ arr[i].substr(0,1), arr[i] });
		umm.insert({ arr[i].substr(0,2), arr[i] });
		umm.insert({ arr[i].substr(0,3), arr[i] });
	}
}

int main() {
	init();

	string s;
	cin >> s;

	auto mi = umm.equal_range(s); //s를 만족하는 범위

	for (auto i = mi.first; i != mi.second; ++i) { // ++i가 i++ 보다 빠름
		cout << i->second << " ";
	}

	return 0;
}

(원래 자동완성 기능 알고리즘 : 트라이라는 알고리즘, 코테에 가끔 등장)

Hash 속도

Hash 등록할 때 걸리는 속도 + (Hash 펑션 속도) + Hash 검색할 때 걸리는 속도

여기서 ++i를 쓰는 이유

unordered multimap을 출력할 때
i++ 말고 ++i를 쓰는 이유
-> 다른데서는 속도가 똑같은데, STL에서는 i++보다 ++i가 빨라서 ++i를 쓴다.

해시 예제

문제 : 숫자 배열 4개가 주어져있고, 그 배열에서 숫자를 하나씩 뽑아서 더했을 때 총합이 0이 되는 조합이 몇개인지 찾아라
4중 for문 돌릴 때의 문제점 : 숫자 배열의 크기가 1000이라고 가정할경우 시간초과
DAT로 풀때의 문제점 : 숫자 하나가 1억이 넘어갈 수도 있어서 안됨
결론 : 해시로 풀어야하는 문제!!
설계 : 이중 for문을 각각 돌려서 두 배열씩 합을 Hash로 저장해놓고, (합을 인덱스로 쓰고, 그게 몇개인지를 개수로 등록해놓아야 함.) 이중 for 문을 다시 돌려서 합이 0인걸 세기.
-> 11일때, -11을 찾고 걔가 없으면 11을 탈락시키는 방식!!!

map VS multimap 판단 작은 팁...
multimap은 해시에 값을 넣을때 insert로만 넣을 수 있어서..
중간에 연산을 하고 그 값을 해시에 더해줘야 하는 경우 map이 더 적합
(근데.. 다시 생각해보니 multimap이어도 전역변수를 하나잡고 거기에 ++을 하고 걔를 insert 해주면 될 듯..?)

유리