boj 7785번 문제를 통해 접하게된 unordered_set과 sort에 관하여.

처음으로 unordered_set을 사용하여서 문제를 해결해보려 했을때, boj 7785번 문제에 대한 코드를 떠올려 본것을 첨부해보면, 

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

int n;
unordered_set<string> worker;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    string name;
    string state;
    while(n--){
        cin>>name>>state;
        if(state=="enter"){
            worker.insert(name);
        }
        if(state=="leave"){
            worker.erase(name);
        }
    }
    sort(worker.begin(),worker.end(),greater<>());
    for(auto e:worker) cout<<e<<'\n';
}

이와 같다. 

근데 이 코드를 돌려보면 에러 메세지를 얻게 된다. 

/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/
include/c++/v1/__algorithm/sort.h:211:46: error: invalid operands to binary 
expression ('std::__hash_const_iterator<std::__hash_node<std::string, void *> *>' 
and 'int')

대략적으로 위와 같은 형태인데, 

이에 대해서 힌트를 얻기 위해서 gpt에 검색을 해보았다.

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

int n;
unordered_set<string> worker;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    string name;
    string state;
    while(n--){
        cin >> name >> state;
        if(state == "enter"){
            worker.insert(name);
        }
        if(state == "leave"){
            worker.erase(name);
        }
    }
    
    vector<string> sortedWorker(worker.begin(), worker.end()); // unordered_set을 vector로 복사
    sort(sortedWorker.begin(), sortedWorker.end(), greater<>()); // vector를 정렬
    
    for(auto e : sortedWorker)
        cout << e << '\n';
}

 

"unordered_set은 내부적으로 해시 테이블을 사용하여 원소를 저장하므로, 정렬되지 않은 상태로 유지됩니다. 따라서 sort 함수를 직접 적용할 수 없습니다."

 

결국 핵심은 hash 자료구조를 사용하여서 구현한 unordered_set의 경우 정렬을 할 수 없다는 것으로 보여진다. 그래서 unordered가 붙어 있는 것이라고 연관지어서 기억해도 좋을것 같다. 

그래서 이런식으로 직접적으로 unordered_set 으로 선언된 worker를 직접적으로 sort 하려니까 문제가 발생하는 것이고, 

그걸 방지하기 위해서는 내부 원소들을 복사해서 sort를 할 수 있는 컨테이너에 담은뒤, 거기서 sort를 해서 출력을 해주어야 한다는 것이다. 

그래서 내가 참고하기 위해서 본 코드에서도 나와 똑같은 형태로 쭉 진행되는데, 

vector<string> ans(s.begin(),s.end()); 형태의 코드가 추가되어서, unordered_set에 있는 값들을 복사해와서 vector를 만든뒤, 그 vector를 sort하는 코드가 있다. 

앞으로 unordered가 붙은 set, multiset, map, multimap을 사용할때는 sort를 해서 출력해주어야 하는 경우는, 이렇듯 새로운 컨테이너를 선언해서 원소들을 복사한뒤에 새로운 컨테이너를 정렬하는 방법을 떠올리도록 하자. 

 

**unordered가 붙어 있는 이유를 꼭 생각하면서 기억하고 문제를 풀도록 하자**