[C++] STL 자료구조: unordered_set, unordered_map

<unordered_set, unordered_map과 set, map>

- 이름에서 알 수 있듯이 내부 원소들이 정렬되어있지 않다는 점에서 unordered_set, unordered_map은 set, map과 차이점이 있다.

- ​unordered_set, unordered_map은 내부적으로 hash table을 사용해 구현되어있다.

hash table은 삽입, 삭제, 검색을 지원하며 hash table의 특징 상 연산의 시간복잡도는 평균 O(1), 최악의 경우 O(n)이다.

이는 BBST로 구현된 set, map의 연산이 O(logn)인 것과 비교했을 때 평균적으로 더 좋다.

- 또한 unordered_set, unordered_map은 set, map과 마찬가지로 원소가 중복될 수 없다. 만약 중복된 원소를 사용하고 싶다면 unordered_multiset, unordered_multimap을 사용한다.

- unordered_set은 해시 함수에 따라 저장 순서가 결정되므로 중복되지 않는 부분 문자열의 개수를 세는 데에 사용되었다면, set은 정렬된 순서로 중복을 제거하여 중복되지 않는 부분 문자열의 개수를 세는 데에 사용된다.

 

unordered_set, unordered_map은 삽입, 삭제, 검색의 시간복잡도가 최악의 경우 O(n)이지만, 평균적으로 O(1)이며 메모리도 set, map보다 일반적으로 적게 사용한다. 따라서 set, map을 사용할 때 내부 원소들이 정렬되어있을 필요가 없다면 set, map 대신 unordered_set, unordered_map을 사용할 수 있다. (성능은 더 좋을 수도 있고, 아닐 수도 있다)

 

##문자열 추출하기

1. set <string> str

    for (int i=0; i<str.size(); i++) // 모든 시작 가능한 위치
        for(int j=1; j<=str.size()-i; j++) // 만들어질 수 있는 문자열 길이 case
            S.insert(str.substr(i,j)); //i=자르기 시작하는 위치, j=추출할 문자열 갯수

2. unordered_set<string> S

    for(int i=1; i<=n; i++) // 추출하려는 문자열의 길이

        for(int k=0; k+i<=n; k++) // 시작위치; 0부터 n-i까지

            S.insert(s.substr(k,i));

여기서 k+i<=n이 되는 이유는 문자열의 길이: n, 부분 문자열의 길이: i라고 할 때, 부분 문자열의 끝 위치는 (k + i - 1)이다.

만약 이 값이 문자열 s의 끝을 넘어가면 부분 문자열을 만들 수 없다. 따라서 k + i - 1이 n - 1보다 작거나 같은 범위에서만 부분 문자열을 생성한다. 따라서 k의 범위는 0부터 n - i 까지가 된다

 

백준)

11478번)

int main() {

fastio;

string s; cin >> s;

int n = s.size();

unordered_set<string> S;

for (int sz = 1; sz <= n; sz++) for (int i = 0; i + sz <= n; i++)

S.insert(s.substr(i, sz));

cout << S.size() << '\n';

}

 

10546번) 참가자 이름이 나열되고 완주자 이름이 나열된다. 완주하지 못한 사람 출력하기 == 홀수번 등장한 문자열 찾기

int main() {

fastio;

int n; cin >> n;

unordered_set<string> S;

for (int i = 1; i < 2 * n; i++) {

string s; cin >> s;

if (S.count(s)) S.erase(s);

else S.insert(s);

}

cout << *S.begin() << '\n';

}

 

17219번)

int main(){

    fastio;

    int a,b;

    cin>>a>>b;

    unordered_map<string, string> M;

    while(a--){

        string m,n; cin>>m>>n;

        M[m]=n;

    }

    while(b--){

        string s; cin>>s;

        cout<<M[s]<<'\n';

    }

}

얘는 map으로 선언해도 괜찮다.