STL set 구조체활용(1) - 사용법(set은 만능이다?)

이번 글에서는 set의 기본 사용법을 알아보도록 하겠습니다. 그리고 마지막에는 Set을 문제 풀이에서 어떻게 사용하면 좋을지 말씀드리겠습니다.

 

1. set이란?

set은 이진탐색트리(Binary Search Tree, BST) 구조로 구성되어 있습니다. 실제로는 BST 중 Red-Black Tree로 구현되어 있습니다. 그래서 최악의 경우에도 삽입,삭제,조회가 O(logN)만에 가능합니다.

참고로 이진탐색 트리는 항상 우선순위가 "왼쪽자식노드<현재자식노드<오른쪽 자식노드"를 만족합니다.  그래서 이진탐색 트리의 내부 원소들은 항상 정렬된 상태를 유지합니다. Set의 경우 우선순위가 같은 원소들은 존재할 수 없습니다. 모든 원소는 유일합니다!!

 

기억해야할 내용을 요약하자면,

1) set은 삽입, 삭제, 조회가 O(logN)만에 가능합니다.

2) set의 모든 원소는 중복이 불가능합니다. (중복이 불가능하다는 말은 우선순위를 비교하는데 사용하는 내부 필드 값들이 모두 동일한 경우가 불가능하다는 것입니다.)

3) set은 첫 원소부터 끝 원소까지 우선순위대로 정렬되어 있습니다.

 

2. STL  set 사용해보기

실제로 문제 풀 때는 구조체를 set의 원소로 많이 사용하므로 구조체를 기준으로 설명하겠습니다. 

 

(1) 정렬 기준 설정하기

operator < 을 구조체 내부에 작성해주면 set의 정렬기준(우선순위)를 설정해 줄 수 있습니다. 아래 코드처럼 사용하시면 됩니다. operator의 코드는 현재 원소와 다음 원소(var)을 비교하는 것이라고 생각하면 됩니다. 그리고 현재 원소가 다음 원소보다 앞에 있기 위한 조건을 적는다고 이해하면 좀 더 쉬울 듯 합니다. 

 

주의) operator < 을 작성할 때 const 절대로 빼먹으면 안됩니다.

주의) operator < 내부에서 return을 명확하게 해줘야합니다. 두 원소를 비교했을 때 동일한 경우는 절대 발생할 수 없도록 내부 코드를 작성해야 합니다. 

#include<stdio.h>
#include<set>
using namespace std;

struct Data {
	int id;
	int p;
	int num;

	//p 큰게 앞으로, p가 같다면 id작은게 앞으로
	bool operator < (const Data &var) const {
		if (p == var.p)return id < var.id;
		return p > var.p;
	}
};

set<Data> mySet;

 

(2) 삽입,  조회,  삭제

begin() :가장 맨 첫 원소를 가리키는 반복자를 리턴합니다.

end() :마지막 원소의 다음을 가리키는 반복자를 리턴합니다(매우 큰 쓰래기 값이라고 보면 됩니다.)

삽입 : insert()함수를 사용합니다. 중복된 원소를 삽입하는 경우 무시됩니다.

조회 : find()함수를 사용합니다. 해당 원소가 set에 존재하면, 그 원소를 가리키는 반복자를 리턴합니다. 만약 찾을 수 없다면 set.end()를 리턴합니다.

삭제 : erase()함수를 사용합니다. 어떤 값을 가진 원소를 삭제시킬 수도 있고, 어떤 반복자가 가리키는 원소를 삭제 시킬 수도 있습니다.

 

주의) 특정 원소가 중복인지를 판단하는 기준은 구조체의 operator < 에서 값 비교에 사용한 필드 값들 입니다. 예를 들어 아래 코드의 경우 "어떤 원소 A의 id와 어떤 원소 B의 id가 같고, 원소 A의 p와 원소 B의 p가 동일하면" 같은(중복인) 원소입니다.

 

주의) 어떤 반복자 iter가 존재할 때, set.erase(iter)을 수행해주면 iter는 바로 set.end()로 변해서 더이상 사용할 수 없습니다. 하지만 set.erase(iter++)을 해주면, 원소를 삭제한 뒤 iter는 삭제된 원소의 다음 원소를 가리키게 됩니다.

#include<stdio.h>
#include<set>
using namespace std;

struct Data {
	int id;
	int p;
	int num;

	//p 큰게 앞으로, p가 같다면 id작은게 앞으로
	bool operator < (const Data &var) const {
		if (p == var.p)return id < var.id;
		return p > var.p;
	}
};

set<Data> mySet;

int main(void) {
	mySet.insert({ 1,1,10 });
	mySet.insert({ 1,2,10 });
	mySet.insert({ 3,3,10 });
	mySet.insert({ 1,3,10 });
	mySet.insert({ 1,3,100 });	//삽입 안됨(id p값 같은게 이미 존재해서 아얘 삽입 안됨)
	mySet.insert({ 1,4,10 });
	mySet.insert({ 2,4,10 });

	for (auto iter = mySet.begin(); iter != mySet.end(); iter++) {
		printf("{id = %d, p = %d, num = %d}\n", iter->id, iter->p, iter->num);
	}
	/*
	{id = 1, p = 4, num = 10}
	{id = 2, p = 4, num = 10}
	{id = 1, p = 3, num = 10}
	{id = 3, p = 3, num = 10}
	{id = 1, p = 2, num = 10}
	{id = 1, p = 1, num = 10}
	*/

	//0번째 원소, 2번째 원소 출력하기
	auto it = mySet.begin();
	printf("0번째 원소 : {id = %d, p = %d, num = %d}\n", it->id, it->p, it->num);	//0번째 원소 : {id = 1, p = 4, num = 10}
	for (int i = 0; i < 2; i++)it++;	//it 2칸 이동
	printf("2번째 원소 : {id = %d, p = %d, num = %d}\n", it->id, it->p, it->num);	//2번째 원소 : {id = 1, p = 3, num = 10}

	//특정 원소 찾기
	auto iter = mySet.find({ 1,1,100 });	//id=1,p=1인 원소 찾음
	printf("찾은 값 : {1, 1, 100}, 실제 값 : {id = %d, p = %d, num = %d}\n", iter->id, iter->p, iter->num);
	//찾은 값 : {1, 1, 100}, 실제 값 : {id = 1, p = 1, num = 10}

	iter = mySet.find({ 3,3,10 });
	if (iter == mySet.end())printf("{3,3,10} 존재 안 함.\n");

	//구조체 직접 만들어서 key에 해당하는 필드들만 초기화 해준 뒤 find()함수에 넣어서 특정 원소 찾을수도 있음.
	Data target;	target.id = 1;	target.p = 2;	//target.num은 쓰래기 값
	iter = mySet.find(target);
	Data temp = *iter;	//이렇게도 쓸 수 있다.
	printf("찾은 값 : {1, 2, ?}, 실제 : {id = %d, p = %d, num = %d}\n", temp.id, temp.p, temp.num);
	//찾은 값 : {1, 2, ? }, 실제 : {id = 1, p = 2, num = 10}

	//삭제하기
	mySet.erase({ 1,5,10 });	//삭제 안됨(같은 id, p값 존재 안함)
	mySet.erase({ 3,3,100 });	//{3, 3, 10} 삭제됨(id, p 값 같은 원소)

	//삭제 후 iterator가 삭제된 원소의 다음 원소를 가리키도록 하기
	iter = mySet.begin();
	mySet.erase(iter++);
	printf("iter가 가리키는 값: {id = %d, p = %d, num = %d}\n", iter->id, iter->p, iter->num);
	//iter가 가리키는 값: {id = 2, p = 4, num = 10}

	return 0;
}

 

(3) 기타 사용법

맨 끝 원소에 접근하는 법: (--set.end())로 접근하면 됩니다. 아니면 set.rbegin()함수로도 접근 가능합니다.

set.upper_bound(특정값): 특정값을 초과하는 첫번째 원소를 가리키는 반복자를 리턴합니다.

set.lower_bound(특정값): 특정값과 크거나 같은 첫 번째 원소를 가리키는 반복자를 리턴합니다.

 

(4) 특정 원소 수정하기

set의 경우, 바로 원소의 값을 수정할 수는 없습니다. 아래의 단계를 거쳐서 수정해야 합니다.

어떤 원소 A를 수정하려는 경우,

1) A를 set에서 찾기 

2) A를 따로 복사해서 B에 저장하기

3) B를 원하는 값으로 수정하기

3) set에서 A 삭제하기

4) set에 B 넣기

시간복잡도 계산하면 상수 다 제외하고 O(logN) 나옵니다.

실제 구현한 코드는 나중에 업로드 하겠습니다.

 

3.  Set을 문제풀이에 활용하기(Set은 만능이다?)

set은 아래와 같은 경우의 문제를 풀 때 활용하면 정말 좋습니다.

"전체 데이터 수가 매우 크고, 삽입,삭제,조회,수정이 많이 발생하는 경우"

set은 삽입,삭제,조회,수정이 O(logN)이고, 전체 데이터가 정렬되어 있으므로 시간초과의 문제에서 많은 경우 벗어날 수 있습니다.

그리고 라이브러리로 주어져있어서 set을 따로 구현할 필요가 없으므로 코드 작성하는데 걸리는 시간을 많이 줄일 수 있습니다.

 

그런데, set으로 다른 자료구조를 대체할 수도 있을 것 같습니다(개인적인 의견입니다). 물론 항상 가능한 건 아닙니다. 문제에 따라 다르긴 합니다!!

 

(1) set으로 Heap 대체하기

-Heap push: O(logN)  → set.insert() : O(logN)

-Heap의 top(루트에 들어있는 원소 값 얻어오기):  O(1) →set.begin() : O(1)

-Heap pop: O(logN)  → set.begin()으로 처음 원소 값 얻고, set.erase()로 처음 원소 삭제하기 : O(logN)

-Heap의 특정 원소 삭제: O(logN) → set.erase()로 특정 원소 삭제하기: O(logN)

-Heap의 특정 원소 업데이트: O(logN) → set 특정원소 수정하기: O(logN)

 

주의) set은 원소 중복이 불가능하지만, heap은 원소 중복이 가능합니다. 원소 중복이 가능한 경우에는 set 말고 multiset을 쓰면 됩니다.

 

주의) 위에 시간복잡도는 동일하지만 생략된 상수의 경우 set이 Heap보다 훨씬 큽니다. 그래서 실제로는 set이 Heap보다 느리긴 합니다. 하지만 이정도의 시간차이가 큰 영향을 미치지 않는 문제라면, 코드가 훨씬 짧은 set을 활용하는 편이 시험에서는 유리할 것 같다는 생각이 듭니다.

(참고자료: https://codeforces.com/blog/entry/69230)

 

(2) set  vs  링크드리스트

-LinkedList 특정 노드 찾기:

(id 기준으로 노드 가리키는 포인터를 unordered_map에 저장한 경우)O(1)  → set.find() : O(logN)

 

-LinkedList 특정 노드 삽입: O(1) → set.insert() : O(logN)

 

-LinkedList 특정 노드 삭제: O(1) → set.erase() :O(logN)

 

-LinkedList 특정 노드 값 변경: O(1) → set 특정원소 수정하기 : O(logN)

 

-N개의 데이터를 이용해서 특정 기준으로 정렬된 자료 만들기

(LinkedList) : 들어갈 위치 찾고 삽입해주면 됩니다, 시간복잡도=O(1)+O(2)+...O(N-1) = O(N*N)

(set) : N개 그냥 삽입해주면 됩니다, 시간복잡도=O(N*logN)

 

문제에 따라서 링크드 리스트가 유리한 경우가 있고, set이 유리한 경우가 있으므로, 문제를 잘 분석해서 링크드 리스트를 쓸지, set을 쓸지 결정해야 합니다. 다만 시간초과의 문제에서 자유롭다면, set이 링크드리스트보다는 코드길이와 구현 난이도가 훨씬 낮으므로 set을 쓰는 것도 괜찮을 거 같습니다.

 

set은 많은 문제에서 사용할 수 있는 좋은 도구입니다. 하지만 항상 그렇지는 않을수도 있으니 시간복잡도 분석을 잘 해본 뒤 사용해야 합니다.

 

다음 글에서는 구조체에서 정렬기준을 설정하는 여러가지 방법을 알아보고 해당 코드의 의미도 알아보도록 하겠습니다.

2023.03.30 - [STL] - STL set 구조체 활용 (2)- 정렬 기준 바꾸기

STL set 구조체 활용 (2)- 정렬 기준 바꾸기

2023.03.30 - [STL] - STL set 구조체 활용(3) - set에 구조체 포인터 담기

STL set 구조체 활용(3) - set에 구조체 포인터 담기