[면접을 위한 CS 전공지식 노트][자료구조] Set

1. Set이란?

 자료구조인 SET은 수학에서의 집합을 구현해놓은 것이다. 집합은 중복되지 않는 원소들의 모임으로 수학적인 집합 개념을 컴퓨터 과학의 문제에 적용하기 위해서 만들어진 자료구조 이다. Set은 다음과 같은 특징을 가지고 있다.

 

SET의 주요 특징

 1) 고유한 원소: Set은 각 원소가 중복되지 않는다. Unique한 원소.

 2) 순서 없음: Set에서는 원소의 순서를 보장하지 않는다. 순서가 없다.

 3) 집합 연산: Set은 원소들 간의 합집합, 교집합, 차집합 등과 같은 집합연산을 지원한다.

2. JAVA에서의 Set

 1) HashSet

   가장 일반적으로 사용되는 Set 구현체 이며, 해시테이블을 기반으로 구현되어 있다.

 

   HashSet의 주요 특징

   - 순서를 보장하지 않는다.

   - 추가, 삭제, 조회 연산이 평균적으로 O(1)의 시간복잡도를 가진다. (해시기반)

   - 순서가 중요하지 않거나 중복을 허용하지 않는 집합을 다룰 때 적합하다.

 

 2) LinkedHashSet

   HashSet과 비슷하지만, 원소들의 입력 순서가 유지되는 특징을 가지고 있다.

 

 LinkedHashSet의 주요 특징

  - 원소들의 입력 순서가 보장 된다.

  - 각 원소가 이전과 다음 원소와의 연결을 유지하면서, 원소의 추가, 삭제, 조회연산이 O(1)의 시간복잡도를 가진다.(해시 기반)

  - 순서가 중요하지만 중복을 허용하지 않는 집합을 다룰 때 적합하다.

 

 3) TreeSet

  이진 탐색 트리를 기반으로 구현되어, 원소들이 정렬된 상태로 저장한다.

 

  TreeSet의 주요 특징 

  - 원소들의 정렬된 상태로 저장된다.

  - 이진 탐색 트리로 구현되어 있기 때문에 원소의 추가, 삭제, 조회 연산 시 O(logn)의 시간복잡도를 가진다.(이진 트리 기반)

  - 원소들의 정렬이 필요하면서 중복을 허용하지 않는 집합을 다룰 때 적합하다.

 

 

4) Set 인터페이스의 주요 메서드

- boolean add(E e)

    주어진 원소 'e'를 집합에 추가, 이미 존재하는 원소라면 추가하지 않고, false를 리턴한다.

- boolean remove(Object object)

    주어진 객체 'o'와 일치하는 원소를 집합에서 제거, 원소가 제거되면 true를 반환하고, 원소가 존재하지 않으면 false를 반환한다.

- boolean contains(Object o)

    주어진 객체 'o'가 집합에 포함되어 있는지 여부를 확인 포함되어 있으면 true, 없으면 false.

- int size()

    집합에 포함된 원소의 개수를 반환.

- boolean isEmpty()

    집합이 비어 있으면 true, 아니면 false.

- void clear()

    집합을 모든 원소를 제거하여 비운다.

- Iterator<E> iterator()

    집합의 원소들을 순회하기 위한 반복자(Iterator)를 반환.

- boolean addAll(Collection<? extends E> c)  - 합집합

    주어진 컬렉션 'c'에 포함된 모든 원소를 집합에 추가.

- boolean removeAll(Collection<? extends E> c) - 차집합

    주어진 컬렉션 'c'에 포함된 모든 원소를 집합에서 제거.

- boolean retainAll(Collection<?> c) - 교집합

    주어진 컬렉션 'c'에 포함된 원소들과 교집합을 구하여 집합을 수정한다. 즉, c에 포함되지 않은 원소들은 집합에서 제거.

- Object[] toArray()

    집합의 원소들을 object 배열로 반환.

- <T> T[] toArray(T[] a)

    지정된 배열 'a'에 집합의 원소들을 복사하여 반환한다. 배열의 길이가 집합의 크기보다 작으면 새 배열이 생성. 

 

3. 정리

- Set은 원소가 Unique한 자료구조이다.

- 일반적으로 많이 쓰는 HashSet은 순서를 보장하지 않으나, 입력순서 또는 정렬을 이용하고 싶다면 LinkedHashSet 또는 TreeSet을 사용하면 된다.

- 중복을 허용하지 않는 데이터를 다룰 때 유용하다.

- 집합 연산이 필요할 때 이용할 수 있다.

 

참조

면접을 위한 CS 전공지식 노트