[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으로 선언해도 괜찮다.