백준 7785 회사에 있는 사람

문제 출처
https://www.acmicpc.net/problem/7785

오답원인
벡터 자료형을 사용하여 해결하려고 한 것.
벡터 자료형의 erase 를 사용할 때 최악의 경우 시간복잡도가 O(n)이라고 한다.

내가 작성한 코드의 시간복잡도는 O($n^2$)이다. 문제에서 제시한 n의 범위가 $2<n<10^6$ 이므로 내가 작성한 코드는 최악의 경우 $10^{12}$ 번을 수행하게 된다.
문제에서 제시한 제한시간은 1초, 약 1억($10^8$)회 이기 때문에 시간초과로 틀렸다.

이를 해결하려면 vector 가 아닌 다른 자료구조를 사용하여 해결해야 한다.
위에서 erase 의 시간복잡도가 O(n)인데 시간초과를 하므로 더 짧은 O($logN$) 알고리즘을 사용해야함을 알 수 있다.
사실 문제 카테고리가 hash, map 이라고 나와 있으므로 hash map(unordered map) 또는 map 을 사용하여 풀면 된다.

수정 후 코드

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    map<string, bool, greater<string>> list; // 세 번째 인자에 greater<key의 자료형> 을 주면 내림차순 으로 정렬 된다.
    string name, flag;
    int n;
    cin >> n;
    
    for(int i = 0; i < n; ++i) {
        cin >> name >> flag;
        
        if(flag.compare("enter") == 0)
            list.insert({name, true});
        else {
            list.erase(name);
        }
    }
    // 출력
    for(auto iter = list.begin(); iter != list.end(); iter++) {
        cout << iter->first << "\n";
    }
    
    return 0;
}