백준 7785 - 회사에 있는 사람

입력된 이름과 상태에서 조건에 맞는 이름만 출력해야 하는 문제입니다.

이름과 상태를 저장할 수 있어야 하기에 c++ STL 컨테이너의 map을 이용해 해결했습니다.

map 특징

map은 각 요소가 key와 value로 이루어진 트리입니다. 내부적으로 레드-블랙 트리로 구현되어 있어 삽입,삭제,검색의 시간복잡도가 O(log n)으로 상당히 우수한 실행시간을 보여줍니다.

map은 기본적으로 입력된 key들에 대해 오름차순으로 정렬합니다. 이 문제에서는 내림차순으로 정렬해야 하므로 std::greater를 이용해 내림차순으로 정렬하도록 설정했습니다.

map은 중복을 허용하지 않아 중복된 노드는 삽입되지 않습니다. map의 find 함수를 이용해 이미 있는 key인지 확인했습니다.

#include<iostream>
#include<map>

int main()
{
	std::cin.tie(NULL);																							// cin과 cout을 묶지 않음
	std::ios_base::sync_with_stdio(false);																		// C, C++ 표준 stream 동기화 비활성

	int n;
	std::cin >> n;
	std::cin.ignore();

	std::map<std::string, bool, std::greater<std::string>> persons;												// 내림차순 정렬(map은 기본 오름차순)

	for (int i = 0; i < n; i++)
	{
		std::string name, state;
		std::cin >> name >> state;

		auto iter = persons.find(name);																			// map에서 name 탐색해서 iterator 반환
		if (iter == persons.end())
		{
			bool enter = state.compare("enter") == 0;
			persons.insert(std::make_pair(name, enter));														// map 삽입
		}
		else
		{
			bool enter = state.compare("enter") == 0;
			iter->second = enter;																				// map value 변경
		}
	}

	for (auto iter = persons.begin(); iter != persons.end(); iter++)											// map for로 끝까지 탐색
		if (iter->second)
			std::cout << iter->first << "\n";

	return 0;
}