[BOJ] #7785 회사에 있는 사람

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

7785번: 회사에 있는 사람

---

결과적으로 set을 사용하면 아주 쉽게 풀수있었던 문제인데, vector, 그것도 pair형 vector를 선언하고 탐색 및 삭제를 알아보다가 시간초과가 났고, 계속 구글링을 하며 돌파구를 찾아보다가 시간을 많이 버린 문제이다. 반복문 안에서 O(N)짜리 erase와 remove를 때리고 있으니 시간초과가 안나는것이 이상하지. 처음부터 set으로 가닥을 잡고 들어갔으면 10분 안에 풀어버렸을 문제인듯 한데 너무 아쉽다. 애초에 문제 난이도도 실버5짜리 문제이기에 출제자의 의도또한 그냥 set 메소드를 얼마나 잘 사용할 수 있는지만 알아보는 문제인것같다. 군대에서 머리가 많이 굳었구나. 아직 실력이 매우 처참하다. 하지만 이렇게 문제를 딱 보고 어느 알고리즘, 어느 자료구조를 적용해야 할지 한눈에 알아보는것이 PS실력이기에 많이 반성하고 공부해야 할듯하다.

#include <iostream>
//#include <vector>
#include <set>
#include <string>
#include <algorithm>

using namespace std;

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

    int N;
    cin >> N;

    /*vector<string> v;

    while(N-->0) {
        string name, cmd;
        cin >> name >> cmd;

        if (!cmd.compare("enter")) {
            v.push_back(name);
        }
        else if (!cmd.compare("leave")) {
            v.erase(remove(v.begin(), v.end(), name),v.end());
        }
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    for (string s : v) cout << s << '\n';*/
    //vector로 풀면 O(N^2)가 나와 시간초과 발생
    //set으로 풀자...

    set<string> s;
    
    while(N-->0) {
        string name, cmd;
        cin >> name >> cmd;

        if (!cmd.compare("enter")) s.insert(name);
        else s.erase(name);
    }
    //reverse(s.begin(), s.end());

    set<string>::reverse_iterator rit;
    for (rit = s.rbegin(); rit != s.rend(); rit++) 
        cout << *rit << "\n";

    return 0;
}

코드에서 주석처리된 부분이 처음에 vector로 똥고집 피우다 한참 헤맨 코드다. 이후에 set을 이용하여 바로 풀었다.

---

vector에서 특정한 값 탐색하여 삭제하기

v.erase(remove(v.begin(), v.end(), name),v.end())

erase 함수는 (특정위치1 ~ 특정위치2) 까지 범위의 값 혹은 특정 인덱스 위치를 넣어주면 그에 해당하는 값을 지워준다.\
remove 함수는 (특정위치1 ~ 특정위치2) 까지 범위의 값들을 지운 후, 원래 있었던 vector size만큼 그 범위에 해당하는 값들을 대신해서 채워준다. 이후, 지우고 난 위치의 그 다음 iterator를 reture한다.
erase와 remove는 이렇게 같은 듯 다른 함수이고, 각자의 장단점이 명확하니 잘 알고 써야한다.

따라서, vector 내 특정한 값을 탐색하여 그 값만 지우고 싶다면, remove 함수로 지울 위치를 잡고 그 부분부터 erase 로 싹 지우면 벡터에서 index 위치를 사용하지 않고 특정 값을 지울 수 있다.

set 내림차순 정렬하기

set<string>::reverse_iterator rit;

for (rit = s.rbegin(); rit != s.rend(); rit++)

cout << *rit << "\n";

이번 문제에서 요구하는 출력값은 내림차순으로 정렬한 결과였다. 문제에서 set을 사용하여 풀었는데, set은 insert와 동시에 내부에서 자동으로 오름차순 정렬을 만들어준다. 이를 다시 내림차순으로 바꾸기 위해서는 reverse_iterator를 선언하여 출력할때의 범위를 rbegin()부터 rend()까지로 잡아주고 출력하면 된다. 오름차순의 reverse형태가 내림차순이기에 굳이 바꾸려고 하지말고 앞뒤 포인터만 바꾸어 출력하면 쉽다.
* 참고로 vector형과는 달리 set이나 map은 reverse함수를 사용하면 컴파일 오류가 난다. 따라서, reverse_iterator를 선언하여 역순으로 출력하게 된 것이다.