문제
Set은 말 그대로 집합이다.
자료의 삽입, 삭제, 검색 등을 O(log n)만에 처리해주는 자료구조이다.
Heap을 처음 배울 때는 내부 구조를 직접 구현해보는 과정을 거쳤던 기억이 있을 것이다.
그러나 Set의 경우는 내부 구조가 너무 어려우므로, 사용방법을 익히는 것만으로도 충분하다.
(Set의 내부 구조를 지금 당장 이해하기는 너무 어려우나, 자신이 “궁금증을 해결하지 못하면 불면증에 걸리는 스타일”이라면, 추후에 Red and Black Tree라는 것을 검색해보길 바란다.)
오늘은 맛보기만
우선 Set의 기본적인 사용방법은 다음과 같다. 우선 원소의 삽입, 삭제와 전체 원소를 출력하는 작업만 연습해 보자.
#include <stdio.h>
#include <algorithm>
#include <set> //set을 사용하려면 이 헤더파일이 필요하다.
using namespace std;
int main()
{
set<int> s; /// int형 자료를 넣을 수 있는 집합 s를 하나 만든다.
s.insert(3); /// 집합 s에 3을 넣는다.
s.insert(5);
s.insert(3); /// 3이 이미 있으므로, 이 삽입작업은 아무 효과가 없다.
s.insert(6);
s.insert(9);
s.insert(2);
s.erase(3); ///집합에서 3을 삭제.
s.erase(10); ///집합에 10이 없으므로 이 삭제작업은 무효하다.
for(int element: s){
printf("%d " , element);
}
return 0;
}
마지막 부근의 for문은 “s의 모든 원소 element에 대해 순회하라” 라는 뜻인데, for문의 또 다른 용법 중에 하나이다. 배열이나 vector 등에서도 쓸 수 있으므로, 아직 모르고 있었다면 익혀두는 것이 좋다.
출력결과는 아래와 같다.
2 5 6 9
자세히 보면, 원소 삽입 순서에 상관없이 크기의 오름차순으로 순회한다는 것을 알 수 있다 (5와 6을 먼저 insert했지만, 2가 먼저 출력된다). 이처럼 set은 집합 내의 원소를 항상 정렬된 순서로 유지해준다는 특징이 있는데, 이것이 set의 막강한 장점이며, set 자료구조를 선택하는 주된 이유가 된다.
이제 아래 연습문제를 풀고, 다음으로 넘어가보자.
연습문제
정수형 자료를 저장할 수 있는 집합(set)을 선언한 후, 다음 2가지 작업을 순서대로 처리한 후에 남아있는 자료를 오름차순으로 출력하는 프로그램을 작성하라
i □ : □가 없다면 집합에 추가한다.
r □ : 집합 내에 □가 있다면 삭제한다. 없다면 아무 것도 하지 않는다.
반드시 지금 배운 set을 사용한다.
입력
첫 줄에 작업의 개수인 Q가 주어진다(1≤Q≤100,000)
다음 Q줄에 걸쳐, 위 형식에 맞는 작업이 주어진다. 이때 원소로써 주어지는 정수는 -10억 이상, 10억 이하이다.
출력
모든 작업이 순서대로 끝난 후 set에 남아 있는 원소를 오름차순으로 출력한다.
예제1
10
i 3
i 5
i -4
r 0
i 3
r 3
i 3
r 5
r -5
i 0
-4 0 3
지금은 set<int>만 사용해 보았다. 즉, 정수의 집합을 선언하고, 사용해 본 것이다.
int 외에도 어떤 자료형이든 사용할 수 있다고 생각할 수 있으나, 눈치 빠른 사람들은 이미 알았겠지만, 그렇지 않다.
왜냐하면, "정렬된 순서를 유지한다"는 특성 때문이다. 즉 set<이 안>에 들어갈 수 있는 자료형은 적어도 크기 비교가 가능해야 한다는 점을 잊지 말자.
중복이 허용되는 set을 사용하고 싶으면 multiset을 사용하면 된다.
사용법은 동일하며, 단지 선언을 할 때 set<int>가 아닌 multiset<int>와 같이 변경해주면 된다.
맴버함수 목록
s.begin();
- 맨 첫번째 원소를 가리키는 반복자를 리턴(참조)한다.
s.end();
- 맨 마지막 원소(의 다음)를 가리키는 반복자를 리턴(참조)한다.
s.clear();
- set의 모든 원소를 제거한다.s.empty();
- set이 비어있는지 확인한다.s.size();
- set의 원소의 개수를 반환한다.s.insert(k);
- 원소 k를 삽입한다. (삽입시에 자동으로 정렬된 위치에 삽입된다)
- return타입은 pair<iterator, bool>으로 pair.first는 삽입한 원소를 가리키는 반복자이고, pair.second는 성공(true), 실패(false)를 나타낸다.s.erase(iter);
- iter 반복자가 가리키는 원소를 제거한다. (제거 후 제거 한 원소 다음 원소를 가리키는 반복자를 리턴한다)s.find(k);
- 원소 k가 있는 위치를 가리키는 반복자를 반환한다.
- 만약 원소 k가 없다면 s.end()를 반환한다.s.lower_bound(k);
- 원소 k 이상의 값을 갖는 첫 원소를 가르키는 구간의 반복자를 반환한다.s.upper_bound(k);
- 원소 k 초과의 값을 갖는 첫 원소를 가르키는 구간의 반복자를 반환한다.s.count(k);
- 원소 k 의 갯수를 반환한다. (set에서는 언제나 0 또는 1이기에 multiset에서 주로 쓰인다)
출처
ohjtgood