Data Structures/Associative Containers

1.2.1 Set

개념

집합은 서로 다른 값을 한 번씩 저장하는 자료구조입니다. 같은 값을 다시 넣어도 원소 수는 변하지 않습니다.

같은 값이 여러 번 주어질 때 서로 다른 값만 모으거나, 특정 값이 이미 등록되어 있는지 확인할 때 사용합니다. 예를 들어 참가 번호가 여러 번 기록된 명단에서 실제 참가자 수를 구하려면 번호를 집합에 넣고 원소 수를 셉니다.

중복 제거

참가 번호 1,2,31,2,3이 집합에 등록되어 있습니다.

1 2 3
▲ [그림 1] 집합에 중복 값 삽입 — 연산 전

번호 33을 다시 등록하면 이미 같은 값이 있으므로 중복 삽입을 무시합니다.

1 2 3
▲ [그림 2] 집합에 중복 값 삽입 — 연산 후

새 번호 44를 등록하면 집합은 {1,2,3,4}\{1,2,3,4\}가 되고, 참가자 수는 44명이 됩니다.

포함 여부 확인

등록된 번호가 {1,2,3}\{1,2,3\}일 때 번호 22의 등록 여부를 조회하면 참, 번호 44를 조회하면 거짓입니다. 이처럼 여러 번 들어오는 조회에 대해 값이 집합에 포함되어 있는지 확인할 수 있습니다.

처리한 번호를 기록할 때도 사용합니다. 번호를 하나 읽을 때마다 집합에 있는지 확인하고, 처음 나온 번호이면 처리한 뒤 집합에 넣습니다. 등록을 취소할 때는 해당 번호를 집합에서 삭제합니다.

언어별 사용법

동작C++JavaPython
값 추가st.insert(x)set.add(x)s.add(x)
포함 여부 확인st.contains(x)set.contains(x)x in s
값 삭제st.erase(x)set.remove(x)s.discard(x)
서로 다른 값의 수st.size()set.size()len(s)

저장 방식과 복잡도

포함 여부 확인과 삽입·삭제가 주된 작업이면 해시 집합을 사용합니다. 원소를 정렬된 순서로 관리해야 하면 정렬 집합을 사용합니다.

원소 수를 KK라고 할 때, 저장 방식에 따른 연산 비용은 다음과 같습니다.

종류C++JavaPython삽입·조회·삭제
해시 집합unordered_setHashSetset평균 O(1)O(1)
정렬 집합setTreeSetset과 sorted로 정렬 결과 생성트리 기반 구현은 O(log⁡K)O(\log K)

Python의 sorted(s)는 집합 원소를 정렬한 리스트를 반환하며 O(Klog⁡K)O(K\log K)가 걸립니다.

원소 KK개에 필요한 공간은 O(K)O(K)입니다.

예제

문제

여러 개의 수가 주어진다. 서로 다른 수가 몇 개인지 구하고, 중복을 제거한 수들을 오름차순으로 출력하여라.

입력

첫째 줄에 원소 수 NN이 주어진다. 1≤N≤100 0001\le N\le100\,000이다.

둘째 줄에 수열의 원소 a1,a2,…,aNa_1,a_2,\ldots,a_N이 공백을 사이에 두고 주어진다. 1≤ai<10 0001\le a_i<10\,000이다.

출력

첫째 줄에 서로 다른 수의 개수를 출력한다. 둘째 줄에 그 수들을 오름차순으로 공백으로 구분하여 출력한다.

예제 입력

6
3 1 3 2 1 5

예제 출력

4
1 2 3 5

예제 코드

C++20

#include <iostream>
#include <set>

using namespace std;

int main() {
    int n, i, x;
    set<int> st;
    bool ok;

    cin >> n;

    for (i = 0; i < n; ++i) {
        cin >> x;
        st.insert(x); // 중복 값은 한 번만 저장
    }

    cout << st.size() << '\n';
    ok = true;
    // 정렬 집합의 원소를 오름차순으로 출력
    for (int v : st) {
        if (!ok) cout << ' ';

        cout << v;
        ok = false;
    }

    cout << '\n';
}