Set

set은 중복되지 않는 원소를 정렬된 상태로 저장하는 자료구조이다.

같은 값을 여러 번 추가해도 하나만 저장되며 원소의 존재 여부를 빠르게 확인할 수 있다.

헤더 파일

set을 사용하려면 다음 헤더 파일을 포함해야 한다.

#include<set>

보통 PS에서는 여러 표준 라이브러리를 한 번에 포함하기 위해 다음 헤더 파일을 사용한다.

#include<bits/stdc++.h>

선언

빈 set은 다음과 같이 선언한다. $O(1)$

set<int> s;

위 코드는 int 자료형의 원소를 저장하는 set을 생성한다.

set의 원소는 기본적으로 오름차순으로 정렬된다.

원소가 문자열이라면 사전순으로 정렬된다.

원소 추가와 삭제

원소를 추가할 때는 insert()를 사용한다. $O(\log n)$

s.insert(30);
s.insert(10);
s.insert(20);
s.insert(20);

위 코드를 실행하면 set에는 10, 20, 30이 저장된다.

원소는 자동으로 정렬되며, 이미 존재하는 20을 다시 추가해도 중복으로 저장되지 않는다.

원소를 삭제할 때는 erase()를 사용한다. $O(\log n)$

s.erase(20);

존재하지 않는 원소를 삭제해도 아무 일도 일어나지 않는다.

원소 탐색

특정 원소가 존재하는지는 count()로 확인할 수 있다. $O(\log n)$

if(s.count(20)) {
    cout << "exist";
}

count()는 원소가 존재하면 1, 그렇지 않으면 0을 반환한다.

원소 순회

범위 기반 for문을 사용하면 저장된 원소를 순서대로 확인할 수 있다. $O(n)$

for(int x:s) {
    cout << x << ' ';
}

원소는 정렬된 순서로 출력된다.

배열이나 vector와 달리 인덱스를 이용해 원소에 직접 접근할 수는 없다.

정렬 기준 변경

정렬 기준을 지정하면 내림차순으로 정렬할 수도 있다.

set<int, greater<int>> s;

크기 확인

현재 저장된 원소의 개수는 size()로 확인한다. $O(1)$

cout << s.size();

비어 있는지는 empty()로 확인한다. $O(1)$

if(s.empty()) {
    cout << "empty";
}

empty()는 원소가 하나도 없으면 true, 그렇지 않으면 false를 반환한다.

모든 원소를 삭제할 때는 clear()를 사용한다. $O(n)$

s.clear();

unordered_set

unordered_set은 set과 마찬가지로 중복되지 않는 원소를 저장하는 자료구조이다.

set과 달리 원소를 정렬하지 않으며 삽입, 삭제, 탐색을 평균 $O(1)$에 수행한다.

헤더 파일

unordered_set을 사용하려면 다음 헤더 파일을 포함해야 한다.

#include<unordered_set>

선언

빈 unordered_set은 다음과 같이 선언한다. $O(1)$

unordered_set<int> s;

원소 추가와 삭제

원소를 추가할 때는 insert()를 사용한다. 평균 $O(1)$

s.insert(30);
s.insert(10);
s.insert(20);

원소를 삭제할 때는 erase()를 사용한다. 평균 $O(1)$

s.erase(20);

원소 탐색

특정 원소가 존재하는지는 count()로 확인할 수 있다. 평균 $O(1)$

if(s.count(20)) {
    cout << "exist";
}

연습 문제

C++ Set

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    set<int> s;
    int q; cin >> q;
    while(q--) {
        string op; int x; cin >> op;
        if(op=="insert") {
            cin >> x;
            s.insert(x);
        } else if(op=="erase") {
            cin >> x;
            s.erase(x);
        } else if(op=="count") {
            cin >> x;
            cout << s.count(x) << '\n';
        } else if(op=="size") {
            cout << s.size() << '\n';
        } else if(op=="empty") {
            cout << s.empty() << '\n';
        } else {
            s.clear();
        }
    }
}