BOJ
[백준 C++] 7785번 회사에 있는 사람
FINNN
2019. 5. 15. 12:08
7785번: 회사에 있는 사람
문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성
www.acmicpc.net
문제 유형 : set
시간 복잡도 : nlogn
아래와 같이 n과 n만큼의 출퇴근 로그가 주어진다. 로그는 직원의 이름과 enter 혹은 leave로 주어지며, 현재까지의 로그를 봤을 때 회사에 남아있는 사람의 이름을 출력하는 문제다. 단, 내림차순으로 출력해야 한다.
4
Baha enter
Askar enter
Baha leave
Artem enter
1. 로그는 규칙이 있다. 이름과 enter 사이에 스페이스가 하나 있다는 것이다. 이 규칙을 활용해 두 string 변수를 선언해 입력받고, 두 번째 스트링이 무엇이냐에 따라 set에 해당 이름을 추가하거나, set에서 이름을 삭제하면 된다.
2. set은 오름차순으로 정렬되어 있기 때문에, 내림차순으로 출력하기 위해 rbegin이라는 iterator를 사용했다.
#include <iostream>
#include <set>
#include <string>
using namespace std;
set<string> s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string name, ent;
cin >> n;
while (n--) {
cin >> name >> ent;
if (ent[0] == 'e') s.insert(name);
else s.erase(name);
}
auto iter = s.rbegin();
for (; iter != s.rend(); iter++) {
cout << *iter << '\n';
}
}