BOJ 7785 (회사에 있는 사람)

• 문제
  상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
  
  각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
  
  상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.
  
  회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.
  
  
• 출력
  현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<functional>
using namespace std;
int logCount;
map<string, string, greater<string>> entranceLog;

void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void solve() {
	cin >> logCount;
	for (int i = 1; i <= logCount; i++) {
		string name, act;
		cin >> name >> act;
		if (act == "enter")
			entranceLog.insert(make_pair(name, act));
		else
			entranceLog.erase(name);
	}
}

void print() {
	for (auto iterator = entranceLog.begin(); iterator != entranceLog.end(); iterator++) {
		cout << iterator->first << '\n';
	}
}

int main() {
	fast_io();
	solve();
	print();
	return 0;
}

   입력의 크기가 100만이기 때문에 o(N^2) 이상의 풀이를 사용하면 시간 초과가 나올 것이다. 이 문제는 사원이 나가고 들어오고를 기록해야해서 map 이나 set 자료구조를 사용하면 쉽게 해결할 수 있다.

위의 풀이에서는 map 자료구조를 사용하여 enter이 입력되면 insert, leave가 입력되면 erase 함수를 호출하였다.

functional 헤더에 있는 greater을 사용하면 별도의 compare 함수를 쓰지 않고 내림차순으로 정렬할 수 있다

시간 복잡도 : O(N)

숏코딩 -> set을 이용한 풀이 (기본적으로 오름차순인 것을 rbegin()으로 거꾸로 출력)

#include<bits/stdc++.h>
using namespace std;
set<string> p;
string a,b;
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	while(n--){
		cin>>a>>b;
		if(b[0]=='e')p.insert(a);
		else p.erase(a);
	}
	for(auto s=p.rbegin();s!=p.rend();s++) cout<<*s<<"\n";
}