주니어 백엔드 개발자 인터뷰

# 셋 (Set)

정의

Set은 집합이라는 의미를 가지며, 순서가 없고, 중복되는 요소는 없이 오로지 희소한(unique) 값만 저장하는 자료구조입니다.

image

  • 중복을 허용하지 않아서 같은 값이 계속해서 삽입하게 되면, 마지막에 삽입한 값 하나만 저장됩니다.

# Set을 사용해야하는 이유

  • 집합과 관련한 문제를 해소해야 할 때
  • 중복 처리를 고려해야 할 때
  • 중복 처리와 동시에 빠른 조회가 필요할 때

# 자바에서의 Set

  1. Hash 알고리즘을 이용한 HashSet
  2. 이진 탐색 트리를 사용하여 오름차순 정렬까지 해주는 TreeSet
  3. Set에 순서를 부여해주는 LinkedHashSet

일반적으로 HashSet, TreeSet, LinkedHashSet 순으로 빠릅니다.

# HashSet

  • Hash 알고리즘 기반으로 동작합니다.
  • HashTable 구조를 이용한 HashMap을 이용하여 만들어져 있습니다.

image

  1. 입력된 키를 해시 코드로 변환합니다.
  2. 해시 코드를 인덱스로 한 bucket이라는 array에 해당 인덱스를 찾아 저장합니다.
    (여기서 배열 길이가 초과하는 경우에는 길이의 나머지를 구해 링크드 리스트로 추가합니다.)
  • index가 아닌 key를 이용하여 데이터 저장과 접근이 필요한 경우 사용합니다.
  • 데이터의 크기가 어느 정도 예상되는 경우 사용합니다.
  • 삽입 삭제가 빈번할 경우 사용합니다.
import java.util.HashSet;

// Set 생성하기
HashSet<String> texts = new HashSet<>();

// 데이터 삽입하기
set.add("moosong");

// 값 포함여부 확인하기
boolean isExist = set.contains("moosong"); // 있으면 true, 없으면 false

// 데이터 삭제
set.remove("moosong");

// 데이터 출력
for (String value : set) {
    System.out.println(value);
}
  • HashMap을 이용하여 만들어졌으므로, 저장된 값은 정렬되어 있지 않습니다.

# TreeSet

  • 이진트리의 향상된 버전인 Red-Black Tree를 기반으로 만들어집니다.
  • Tree 구조를 이용한 TreeMap을 이용하여 만들어져 있습니다.

image

  1. 새로운 데이터가 들어오면 루트부터 비교합니다.
  2. 비교의 결과에 따라 우측, 좌측으로 갈지 결정됩니다.
  3. 더 이상 비교를 할 수 없을 때까지 반복합니다.
  4. 추가/삭제는 링크드 리스트 보다 비효율적이지만 검색/정렬은 TreeSet이 더 좋다.
  • 저장되는 데이터의 개수가 몇개인지 예상되지 않는 경우 사용합니다.
  • 삽입과 삭제가 빈번하지 않을 때 사용합니다.
  • 정렬된 값이 필요할 때 사용합니다.
import java.util.TreeSet;

// Set 생성하기
TreeSet<String> texts = new TreeSet<>();

// 데이터 삽입하기
set.add("moosong");

// 값 포함여부 확인하기
boolean isExist = set.contains("moosong"); // 있으면 true, 없으면 false

// 데이터 삭제
set.remove("moosong");

// 데이터 출력
for (String value : set) {
    System.out.println(value);
}
  • TreeMap을 이용하여 만들어졌으므로, 저장된 값은 오름차순으로 정렬되어 출력할 수 있습니다.

# LinkedHashSet

  • LinkedHashSet은 HashSet을 상속하여 만들어진 클래스입니다.
  • 다만 내부는 LinkedHashMap을 이용하여 구현되어 있습니다.
  • 값의 저장된 순서가 중요할 때 사용합니다.
import java.util.LinkedHashSet;

// Set 생성하기
LinkedHashSet<String> texts = new LinkedHashSet<>();

// 데이터 삽입하기
set.add("moosong");

// 값 포함여부 확인하기
boolean isExist = set.contains("moosong"); // 있으면 true, 없으면 false

// 데이터 삭제
set.remove("moosong");

// 데이터 출력
for (String value : set) {
    System.out.println(value);
}
  • LinkedHashMap을 이용하기에, 저장된 값은 저장된 순서대로 출력됩니다.

# Set으로 집합 연산하기

# A가 B의 부분집합인가요?

boolean isContainAll = B.containsAll(A);
  • 부분집합이면 True, 아니면 False

# x가 A의 원소인가요?

boolean isContain = A.contains(x);
  • 원소가 포함되면 True, 아니면 False

# A와 B의 교집합 구하기

TreeSet<String> cloneA = new TreeSet<>(set1);
boolean isModified = cloneA.retainAll(B);
  • 반환값은 cloneA 변경 여부를 반환합니다. -> cloneA에 원소가 존재하지 않는 경우를 제외하고는 항상 True를 반환한다고 보면 됩니다.
  • set.retainAll(collection) 메서드는 원본의 데이터를 변경하므로, 원본 데이터의 손실을 원하지 않는다면 원본을 복사해서 사용해야 합니다.

# A와 B의 합집합 구하기

TreeSet<String> cloneA = new TreeSet<>(set1);
boolean isModified = cloneA.addAll(B);
  • 반환값은 cloneA 변경 여부를 반환합니다. -> cloneA에 원소가 존재하지 않는 경우를 제외하고는 항상 True를 반환한다고 보면 됩니다.
  • set.addAll(collection) 원본의 데이터를 변경하므로, 원본 데이터의 손실을 원하지 않는다면 원본을 복사해서 사용해야 합니다.

# A와 B의 차집합 구하기

TreeSet<String> cloneA = new TreeSet<>(set1);
boolean isModified = cloneA.removeAlll(B);
  • 반환값은 cloneA 변경 여부를 반환합니다. -> cloneA에 원소가 존재하지 않는 경우를 제외하고는 항상 True를 반환한다고 보면 됩니다.
  • set.removeAlll(collection) 메서드는 원본의 데이터를 변경하므로, 원본 데이터의 손실을 원하지 않는다면 원본을 복사해서 사용해야 합니다.

# 참고자료

← 맵(Map) →