[BOJ 7785] 회사에 있는 사람

문제 : 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

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

7785번: 회사에 있는 사람

문제 분석

• 이 문제는 enter가 입력되면 stl에 추가하고, leave가 입력되면 stl에서 삭제한다는 생각으로 접근했다.
• 일단 순서와 상관없이 회사에 있는 사람을 출력하는 코드를 짜고, 이후에 사전의 역순으로 정렬하려 했다.

주의 사항

• 출력할때, 입력된 순이 아니라 사전의 역순으로 출력한다.

vector<string>workers;
int n;
string a,b;
void inOut(const string& name, const string& exist){
    if(exist == "enter"){
        workers.push_back(name);
        return;
    }
    else if (exist == "leave") {
        for(int i=0;i<workers.size();i++){
            if(workers[i]==name) {
                workers.erase(workers.begin()+i);
                return;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    while(n--){
        cin>>a;
        cin>>b;
        inOut(a,b);
    }
    sort(workers.begin(),workers.end(),greater<>());
    for (auto & worker : workers) {
        cout<<worker<<endl;
    }
    return 0;
}

사원의 이름과 상태를 입력해 enter면 workers에 추가 leave면 삭제 -> 내림차순으로 정렬-> 순서대로 출력
논리는 맞는것 같지만 시간초과 가 뜬다.
코드를 살펴보니 반복문에서 선형탐색을 하여 이런 문제가 발생하는게 아닌가 싶다.
그래서 <set>을 사용해 문제를 풀어봤다.

set<string>workers;
int n;
string a,b;
void inOut(string name, string exist){
    if(exist == "enter"){
        workers.insert(name);
        return;
    }
    else {
        workers.erase(name);
        return;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    while(n--){
        cin>>a;
        cin>>b;
        inOut(a,b);
    }
    for_each(workers.rbegin(),workers.rend(),[](string worker) {
        cout<<worker<<endl;
    });
    return 0;
}

<set>은 자동적으로 오름차순으로 원소를 저장하기 때문에 for_each문을 사용해 역순으로 출력하게 했다.
하지만 이번에도 시간초과가 떴다. 
사실 로직도 맞고 코드에 문제가 없어 보였지만 <set>을 잘 알지 못하기에 자신이 없어 다른 stl인 <map>을 사용해 보았다.
(사원들이면 회사에 다시 들어오는 경우도 많아 삭제를 하면 안됐었나 하는 비컴퓨터적인 생각도 했다...)

using namespace std;
map<string, bool> workers;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    while (n--) {//n
        string a, b;
        cin >> a;
        cin >> b;
        workers[a] = (b == "enter"); //
    }
    map<string, bool>::reverse_iterator worker;
    for (worker = workers.rbegin(); worker != workers.rend(); ++worker) {
        if (worker->second)
            cout << worker->first << endl;
    }
    return 0;
}

 

이번에는  <map>에 string을 key로 bool을 value로 설정하여 enter면 true leave면 false로 저장하게 했다.
또, 시간초과가 떴다. 
이 정도면 stl문제가 아니라 다른 문제가 있다는 확신이 들어 이것 저것 자세히 살펴봤다.
문제는 'endl'에 있었다.
endl은 버퍼를 비운다. 반면 개행문자 '\n'은 버퍼를 비우지 않는다. 그렇기에 버퍼를 비우는데 시간이 더 걸린 것이다.
(이 부분이 이렇게 치명적일 줄은 몰랐다...앞으로 알고리즘 문제 풀때 endl쓰면 머리 3번씩 박아야겠다.)

endl->'\n'으로 바꾸니 바로 맞았습니다가 떴다.

#include <iostream>
#include <map>

using namespace std;
map<string, bool> workers;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;

    while (n--) {//n
        string a, b;
        cin >> a;
        cin >> b;
        workers[a] = (b=="enter"); //
    }
    map<string, bool>::reverse_iterator worker;
    for (worker = workers.rbegin(); worker != workers.rend(); ++worker) {
        if (worker->second)
            cout << worker->first << "\n";
    }
    return 0;
}

-> 80ms

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

set<string>workers;
int n;
string a,b;
void inOut(string &name, string &exist){
    if(exist == "enter"){
        workers.insert(name);
        return;
    }
    else {
        workers.erase(name);
        return;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    while(n--){
        cin>>a;
        cin>>b;
        inOut(a,b);
    }
    set<string>::reverse_iterator worker;
    for(worker=workers.rbegin();worker!=workers.rend();worker++){
        cout<<*worker<<'\n';
    }
    return 0;
}

-> 76ms

심지어 <set>을 쓰는게 조금 더 빨랐다.
물론 처음에 <vector>을 이용한 방법은 endl을 '\n'으로 바꿔도 시간초과 가 뜬다.

느낀 점

• 이 문제를 풀며 <map>과 <set>에 대해 제대로 공부하게 됐다. 물론 완벽하게 사용하진 못하겠지만 그래도 map과 set이 어떤 구조인지, 언제 어떻게 사용해야 하는지에 대해 공부하게 됐다.
• 가장 크게 배운것은 endl과 개행문자 '\n'의 차이다. 이 부분때문에 크게 고생했기에 더더욱 확실히 알 수 있게 됐다.

시간복잡도

• 삽입- O(logn)
• 삭제- O(logn)
• 참조- O(logn)
• n번 반복
  ☞ O(n*logn)