B_7785

set/hash/map

set은 연관 컨테이너로, key-value의 구조를 가지는 자료구조이다.
연관 컨테이너는 주로,
- 특정 키가 연관 컨테이너에 존재하는지 유무를 알려주는 기능
- 만일 존재한다면, 이에 대응되는 값을 알려주는 기능
이 대표적인데, C++의 경우 위 두 가지 작업을 모두 처리할 수 있는 '연관 컨테이너'를 제공한다.

전자인 존재유무는 Set/Multiset이 이를 담당하며, 후자인 대응 값 탐색은 Map/Multimap이 담당한다.

set의 특징은 원소의 추가-삭제 작업의 시간 복잡도가 O(logN)으로 굉장히 빠르다는 점이다.
또한, set은 중복된 원소를 허용하지 않으며, 정렬된 상태를 유지한다는 점이 장점이다.
이러한 특성과 더불어, 자체적으로 'find' 메소드를 제공, 컨테이너에 해당 값이 존재하는지 찾는데 이 또한 시간 복잡도가 O(logN)으로 굉장히 빠르다.

이러한 속도가 가능한 이유는 set은 트리 구조이기 때문이다.

맵 또한, Set과 거의 유사하다. 다만 셋의 경우 key 값만 보관하지만 map의 경우 키에 대응되는 value까지도 같이 보관하게 된다.
즉, dictionary를 생각하면 이해가 쉽다.
map의 경우 find 메소드를 사용하면 해당하는 키를 찾아 이를 반환한다!

멀티셋/멀티맵의 경우, 중복을 허용하는 set/map이다.

 

[초기방법] - Timeout

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	vector<string> logger;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string name, log;
		cin >> name >> log;
		if (log == "enter")
			logger.push_back(name);
		else if (log == "leave")
			logger.erase(remove(logger.begin(), logger.end(), name));
	}

	sort(logger.begin(), logger.end(), greater<string>());

	for (int i = 0; i < logger.size(); i++)
		cout << logger[i] << endl;
}

 

[자료구조 set]을 이용한 방법

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

int main(void)
{
	set<string> logger;
	set<string>::reverse_iterator iter;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string name, log;
		cin >> name >> log;
		if (log == "enter")
			logger.insert(name);
		else if (log == "leave")
			logger.erase(name);
	}

	for (iter = logger.rbegin(); iter != logger.rend(); ++iter)
		cout << *iter << "\n";
}