BOJ 7785 : 회사에 있는 사람 (map)

삼성 B형 전체 링크

 

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

 

 

Hash Table / vector를 이용할 필요없이

이름을 key, 회사에 들어있는 상태를 value로 보는 map으로 문제를 풀 수 있다.

map<string, bool> enterMap;

 

하지만 map을 iterator를 이용하여 출력하면, 오름차순 정렬(사전순 정렬)이 된다.

따라서 map의 key가 정렬되는 기준을 변경해줘야 한다.

 

algorithm의 sort에서 정렬 기준을 변경한 것처럼 map도 compare를 만들고 넘겨주면 된다.

struct compare {
	bool operator()(const string& a, const string& b) const
	{
		return a > b;
	}
};

map<string, bool, compare> enterMap;

 

이제 이름에 대해 bool 처리를 해주면 된다.

enter가 입력된 경우에는 해당 key의 value를 true → enterMap[key] = true 로 변경한다.

if (cmd == "enter") enterMap[name] = true; /* enter 입력 */
else  enterMap[name] = false; /* leave 입력 */

 

출력은 for문에서 iterator를 사용하면 된다. value가 true인 경우만 출력하자.

for (map<string, bool>::iterator iter = enter.begin(); iter != enter.end(); iter++)
{
	// iterator->first : key
	// iterator->second : value
}

 

최종 코드는 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <map>

using namespace std;

typedef unsigned long long int ull;

int N;

struct compare {
	bool operator()(const string& a, const string& b) const
	{
		return a > b;
	}
};

map<string, bool, compare> enter;

int main()
{
	string name, cmd;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		cin >> name >> cmd;

		if (cmd == "enter") enter[name] = true; /* enter 입력 */
		else  enter[name] = false; /* leave 입력 */
	}

	for (map<string, bool>::iterator iter = enter.begin(); iter != enter.end(); iter++)
		if (iter->second) printf("%s\n", iter->first.c_str());

	return 0;
}

---

반드시 map이 빠르진 않다.

 

map은 tree이기 때문에 연산 비용(find)이 O(logN)이다.

따라서 문제에서 요구하는 query나 N의 크기 등을 잘 보고 map을 사용하자.