백준/해시

[백준] C++1764 듣보잡

2zreal 2024. 9. 25. 12:10

HashSet과 HashMap에 관해 아직 제대로 알고 있지 못한다. HashSet과 HashMap을 이해하고 익숙해지위해 알고리즘 문제를 풀어보고자 한다.

 

먼저 HashSet은 단일 값을 저장할 때 사용되고, HashMap은 키, 값을 저장할 때 사용된다.

unordered_set<string> hashSet;

unordered_map <string> hashMap; 을 사용하기 위해

 

#include<unordered_set>

#include <unordered_map>를 해준다.

 

hashSet안에 내가 원하는 값이 있는지 확인하기 위해서 find함수를 사용할 수 있다.

find함수는 이터레이터를 돌면서 끝까지 값이 있는지 확인하는 함수이다.

if (hashSet.find(temp)!= hashSet.end()) 만약 원하는 값이 있다면 find함수는 원하는 값의 반복자를 반환한다. 원하는 값이 없다면  hashSet.end()와 같은 값이 반환되어 false가 된다.

 

auto it = hashSet.find("apple"); // unordered_set<string>::iterator it = hashSet.find("apple");

cout<<*it;

 

문제해결방법

1. 먼저 듣지도 못한 사람의 수를 hashSet에 insert 한다.

2. 보도 못한 사람을 입력받고 위 hashSet에 있는지 확인한다. 만약 있다면 result배열에 저장한다.

3.result배열을 사전순으로 정렬한다.(sort함수를 이용해서 사전순으로 정렬이 가능하다.)

 

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

string result[500000];
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	unordered_set<string> hashSet;
	
	int N = 0;
	int M = 0;
	
	cin >> N >> M;
	
	for (int i = 0; i < N; i++)//듣도 보도 못한 사람 입력받음. 
	{
		string temp = "";
		cin >> temp;
		hashSet.insert(temp);
	}

	int count = 0;
	for (int i = 0; i < M; i++)//위 hashSet에 있는지 확인. 
	{
		string temp = "";
		cin >> temp;
		if (hashSet.find(temp) != hashSet.end())
		{
			result[count] = temp;
			count ++;
		}
		
	}

	sort(result, result+count);//result 배열을 사전순으로 정렬.  

	cout << count<<endl;
	for (int i = 0; i < count; i++)
	{
		cout << result[i]<<'\n';
	}

	return 0;
}