(매일 BOJ) C++ 7785번 회사에 있는 사람

이번 문제는 7785번 회사에 있는 사람이다.

접근법

✔ 요구사항

• 같은 사람이 여러 번 출입할 수 있음
• 중복된 출입이나 퇴근은 없음
• 현재 사무실에 남아 있는 사람만 출력
• 출력은 사전 역순

✔ 핵심 아이디어

• 이름을 집합(set) 또는 해시셋(unordered_set)으로 관리하면 삽입/삭제가 빠름
• enter → 이름을 집합에 추가
• leave → 이름을 집합에서 제거
• 최종적으로 남은 사람들을 사전 역순으로 출력

1차코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    long long N;
    cin >> N;
    vector<string> v;

    for(int i = 0; i < N; i++){
        string name, inout;
        cin >> name >> inout;
        if(inout == "enter"){
            v.push_back(name);
        }
        if(inout == "leave"){
            auto a = find(v.begin(),v.end(),name);
            v.erase(a);
        }
    }

    for(int j = 0; j < v.size(); j++){
        cout << v[j] << '\n';
    }
}

 

vector 를 사용하여 TLE 발생 > unordered set 으로 시간복잡도 O(n) > O(1) 로 수정

 

최종코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    long long N;
    cin >> N;
    unordered_set<string> s;
    

    for(int i = 0; i < N; i++){
        string name, inout;
        cin >> name >> inout;
        if(inout == "enter"){
            s.insert(name);
        }
        if(inout == "leave"){
            s.erase(name);
        }
    }

    vector<string> v(s.begin(),s.end());
    sort(v.rbegin(),v.rend());

    for(int j = 0; j < v.size(); j++){
        cout << v[j] << '\n';
    }
}