셋(Set)

1. 셋(Set)이란?

- 셋은 유일한 요소들을 저장하는 자료구조이다.

- 같은 값은 한 번만 저장할 수 있으며 중복되는 데이터를 제거하는 용도로 활용된다.

- 기본적으로 저장 순서에 대해 보장하지 않지만 구현체에 따라 삽입 순서나 정렬된 순서를 유지할 수 있다.

 

2. 해쉬셋(HashSet)

- 해시 테이블을 기반으로 하며, 요소의 해시코드를 이용해 저장 위치를 결정한다.

- 평균적으로 삽입/삭제/검색이 O(1)의 시간복잡도를 가진다.

- 요소가 해시 값에 따라 저장되므로 저장 순서와 조회 순서는 일치하지 않는다.

- 동일한 요소는 한번만 저장된다.

 

2-1. 해쉬셋 주요 메소드

- add(E e): 새로운 요소를 해쉬셋에 추가한다.

HashSet<String> hashSet = new HashSet<>();

hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");

 

- remove(Object o): 해쉬셋에서 특정 요소를 제거한다.

HashSet<String> hashSet = new HashSet<>();

hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");

System.out.println(hashSet.remove("Cherry")); // 출력: true

 

- contains(Object o): 지정된 요소가 해쉬셋에 존재하는지 확인한다.

HashSet<String> hashSet = new HashSet<>();

hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");

System.out.println(hashSet.contains("Banana")); // 출력: true

 

- isEmpty(): 해쉬셋이 비어있는지 확인한다.

HashSet<String> hashSet = new HashSet<>();

hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Cherry");

System.out.println(hashSet.isEmpty()); // 출력: false

 

3. 트리셋(TreeSet)

- 이진 탐색 트리(보통 레드-블랙 트리)를 사용하여 데이터를 정렬된 순서로 저장한다.

- 키의 자연 순서 또는 지정된 Comparator에 따라 항상 정렬된 상태로 저장된다.

- 삽입/삭제/검색 연산이 O(logN)의 시간복잡도를 가진다.

- null을 허용하지 않는다.

 

3-1. 트리셋 주요메소드

- add(E e): 새로운 요소를 트리셋에 추가한다.

TreeSet<String> treeSet = new TreeSet<>();

treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");

 

- remove(Object o): 트리셋에서 특정 요소를 제거한다.

TreeSet<String> treeSet = new TreeSet<>();

treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");

System.out.println(treeSet.remove("Cherry")); // 출력: true

 

- contains(Object o): 지정된 요소가 트리셋에 존재하는지 확인한다.

TreeSet<String> treeSet = new TreeSet<>();

treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");

System.out.println(treeSet.contains("Banana")); // 출력: true

 

- first(): 정렬된 순서에서 가장 첫 번째 요소를 반환한다.

TreeSet<String> treeSet = new TreeSet<>();

treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");

System.out.println(treeSet.first()); // 출력: "Apple"

 

- last(): 정렬된 순서에서 가장 마지막 요소를 반환한다.

TreeSet<String> treeSet = new TreeSet<>();

treeSet.add("Apple");
treeSet.add("Banana");
treeSet.add("Cherry");

System.out.println(treeSet.last()); // 출력: "Cherry"

 

4. 활용 알고리즘

4-1. 중복 제거

- 리스트나 배열에 있는 중복 데이터를 제거하여 유일한 값만 남기는 알고리즘, Set은 중복을 허용하지 않으므로 요소를 넣으면 자동으로 중복이 제거된다.

public class RemoveDuplicates {
	public static void main(String[] args) {
    	// 예제 데이터
    	List<Integer> numbers = Arrays.asList(1, 2, 3, 2, 4, 1, 5);
    
    	// HashSet을 사용하여 중복 제거
        Set<Integer> uniqueNumbers = new HashSet<>(numbers);
        
        // 출력: [1, 2, 3, 4, 5] (HashSet이므로 순서는 보장되지 않음)
        System.out.println(uniqueNumbers);
    }
}

 

4-2. 집합 연산

- 두 집합 간의 합집합, 교집합, 차집합을 구하는 알고리즘

public class SetOperations {
	public static void main(String[] args) {
    	// 예제 데이터
    	Set<String> set1 = new HashSet<>(Arrays.asList("Apple", "Banana", "Cherry"));
        Set<String> set2 = new HashSet<>(Arrays.asList("Banana", "Cherry", "Pineapple", "Watermelon"));
        
        // 합집합: ["Apple", "Banana", "Cherry", "Pineapple", "Watermelon"]
        Set<String> union = new HashSet<>(set1);
        union.addAll(set2);
        System.out.println(union);
        
        // 교집합: ["Banana", "Cherry"]
        Set<String> intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        System.out.println(intersection);
        
        // 차집합(set1-set2): ["Apple"]
        Set<String> difference = new HashSet<>(set1);
        difference.removeAll(set2);
        System.out.println(difference);
    }
}