[C++ STL] SET

나 보려고 정리... 내용 굉장히 러프함 주의...

 

	set	unordered set
언제 사용 ?	원소의 개수가 많아 안정성이 요구될 때	원소의 개수가 적고 빠른 성능이 요구될 때
시간복잡도	O(logN) -> 내부적으로 BST 로직을 따르고 있기 때문	O(1)
정렬 여부 ?	정렬됨, 순서 중요 시 사용	정렬 안됨
원소의 중복을 허용하고 싶을 때	multiset	unordered multiset

// sample code 

#include <cstdio>
#include <set>	// set header 추가해야 한다. 
#include <unordered_set> 	// unordered_set header 추가해야 한다. 


using namespace std;

set<int> SS;
unordered_set<int> US;

int main()
{
	// 0. set 초기화
	S.clear();
    
    
    // 1. 데이터 추가 
    S.insert(1);
    S.insert(2);
    S.insert(3);
    
    
	// 2. iterator for loop
    // begin() : 첫 데이터 
    // end() : 마지막 데이터의 다음 데이터 
    // 만약 해당 컨테이너가 비어있다면 begin() == end()
    // set SS의 가장 처음 데이터부터 마지막 데이터의 다음 데이터를 만나기 전까지 루프를 돌린다. 
    for (auto it = SS.begin(); it != SS.end(); it++) {
    	printf("%d ", *it);
    }
    
    
    // 3. 데이터 탐색
    // find(element)의 리턴값은 iterator의 "주소"
    // O(logN) : BST는 노드가 균등하게 분포해 있기 때문에 뎁스만큼 탐색 시간이 걸린다. 
    // 만약 찾는 데이터가 없으면 SS.end()의 값을 리턴한다. 
    auto it1 = SS.find(7);
    if (it1 != SS.end()) printf("%d\n", *it);
    else printf("none\n");
    
    
    // 4. 데이터 삭제
    // 4-1. erase(element) 의 리턴값은 int, "지워진 원소의 개수"
    // 없는 원소를 지워달라고 하면 아무런 변화 없이 모든 원소가 출력된다. 
    // 있는 원소를 지워달라고 하면 해당 원소를 지우고 다른 원소들은 다 출력된다. 
    int cnt = SS.erase(4);
    printf("%d\n", cnt);
    for (auto it = SS.begin(); it != SS.end(); it++) {
    	printf("%d ", *it);
    }
    printf("\n");
    
    // 4-2. erase(iterator) 의 리턴값은 void
    auto it2 = SS.find(2);
    SS.erase(it2);
    for (auto it = SS.begin(); it != SS.end(); it++) {
    	printf("%d ", *it);
    }
    
    
}

---

[백준 1920] 수 찾기

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

1920번: 수 찾기

#include <cstdio>
#include <unordered_set>
int N, M;

using namespace std;

unordered_set<int> US;

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int n = 0;
		scanf("%d", &n);
		US.insert(n);
	}
}

void is_num(void)
{
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int m = 0;
		scanf("%d", &m);
		if (US.find(m) == US.end()) printf("%d\n", 0);		// set 안에 찾는 데이터 없음 
		else printf("%d\n", 1);								// 찾는 데이터 있음 
	}
}


int main()
{
	input();
	is_num();
	return 0;
}

 

[백준 14425] 문자열 집합 

 

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

14425번: 문자열 집합

#include <iostream>
#include <string>
#include <unordered_set>
int N, M;
int cnt;

using namespace std;

unordered_set<string> US;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		US.insert(s);
	}
}


void is_string(void)
{
	for (int i = 0; i < M; i++) {
		string f;
		cin >> f;
		if (US.find(f) != US.end()) cnt++;		// 해당 문자열이 집합의 원소라면 cnt 증가
	}
}



int main()
{
	input();
	is_string();
	printf("%d\n", cnt);
	return 0;
}