[코드트리] Tree Set

SW중심대학 사업단에서 CodeTree와 함께 실시한 코딩테스트 대비 캠프에 참여하여 공부한 내용을 정리하였습니다.

 

* 참고 : python과 c++, java 등 언어별로 설명이 다른 부분 존재! 필자는 c++ 사용.

 

xxilliant 제작

set STL

C++에서는 set이라는 STL을 이용할 수 있습니다.

set은 TreeSet 자료구조로 되어있으며, 이 TreeSet이 바로 균형 잡힌 이진트리 구조로 데이터들을 관리해주는 자료구조 입니다.

모든 함수의 시간복잡도는 O(logN)입니다.

set을 사용하기 위해서는 #include <set> 헤더와, set<T> name; 형태의 선언이 필요합니다.

T는 타입으로, set 안에 들어갈 원소의 타입을 적어줘야 합니다.

 

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> s;
    return 0;
}

 

set을 이용할 때 자주 사용되는 것은 다음 7가지 입니다. set<int> s;로 선언되어 사용될 때를 예로 설명해보겠습니다.

 

1. s.insert(E)

treeset에 데이터 E를 추가합니다.

 

1. s.erase(E)

현재 treeset에 들어있는 데이터 중 숫자 E를 찾아 제거합니다.

 

1. s.find(E)

현재 treeset에 숫자 E가 들어 있는지를 찾습니다. 있다면 해당 iterator를 반환하며, 없다면 s.end()값을 반환합니다. 따라서 값이 있다면 s.find(E) != s.end(), 없다면 s.find(E) == s.end()를 만족할 것입니다.

 

1. s.lower_bound(E)

E보다 같거나 큰 최초의 숫자가 적혀있는 iterator 값을 반환합니다. 만약 없다면 s.end()값을 반환합니다.

따라서 값을 찾기 위해서는 앞에 *을 붙인 *s.lower_bound(E)를 이용해야 합니다.

 

1. s.upper_bound(E)

E보다 큰 최초의 숫자가 적혀있는 iterator 값을 반환합니다. 만약 없다면 s.end()값을 반환합니다.

따라서 값을 찾기 위해서는 앞에 *을 붙인 *s.upper_bound(E)를 이용해야 합니다.

 

1. *s.begin()

기본적으로 treeset은 오름차순 정렬을 해줍니다. 따라서 treeset의 시작 위치인 s.begin()에 들어있는 값은 treeset에 적혀있는 값들 중 가장 작은 값이 됩니다. 즉, 가장 작은 숫자는 *s.begin()으로 조회가 가능합니다.

 

1. *s.rbegin()

기본적으로 treeset은 오름차순 정렬이므로, treeset에서 가장 큰 값은 가장 마지막 위치에 들어 있을 것입니다.

여기서 s.end()는 treeset의 가장 마지막 원소의 위치가 아니라, 마지막 원소 그 다음을 나타내는 비어있는 끝 위치를 뜻합니다.

가장 마지막 원소의 위치(가장 큰 값)는 실제로 s.rbegin()이며, 최댓값을 얻기 위해서는 *s.rbegin()을 참조해야 합니다.

 

이때, set에 아무 원소가 없는지에 대해서는 s.rbegin() != s.rend()식으로 비교를 진행해야 함에 유의합니다.

 

xxilliant 제작

 

출처 코드트리