Set

HashSet

🍪 중복 불허: HashSet은 집합이므로 중복된 원소를 허용하지 않습니다.

🍪 순서 없음: 원소는 특정한 순서 없이 저장됩니다.

🍪 빠른 검색 및 삽입 속도: 내부적으로 해시 테이블을 사용하여 데이터를 저장하므로, 검색 및 삽입 속도가 빠릅니다.

🍪 Null 원소: HashSet은 null 값을 하나 허용합니다.

🍪 다양한 집합 연산: Set 인터페이스를 구현하기 때문에 집합 연산(교집합, 합집합, 차집합 등)을 기본적으로 지원합니다.

시간 복잡도

• 삽입: ${O(1)}$
• 삭제: ${O(1)}$
• 검색: ${O(1)}$

공간 복잡도

${O(n)}$

메소드

기본 연산

메서드	설명
add(E e)	지정된 원소를 집합에 추가합니다. 원소가 이미 존재한다면 false를 반환합니다.
remove(Object o)	지정된 원소를 집합에서 제거합니다. 원소가 존재하여 제거되면 true를 반환합니다.
contains(Object o)	지정된 원소가 집합에 존재하는지 확인합니다. 존재한다면 true를 반환합니다.
size()	집합의 크기(원소의 수)를 반환합니다.
isEmpty()	집합이 비어 있는지 확인합니다. 비어 있으면 true를 반환합니다.
clear()	집합의 모든 원소를 제거합니다.

집합 연산

메서드	설명
addAll(Collection<? extends E> c)	지정된 컬렉션의 모든 원소를 집합에 추가합니다. (합집합)
removeAll(Collection<?> c)	지정된 컬렉션에 있는 모든 원소를 집합에서 제거합니다. (차집합)
retainAll(Collection<?> c)	지정된 컬렉션에 있는 원소만을 유지하고 그 외의 원소는 제거합니다. (교집합)

기타 메서드

메서드	설명
iterator()	집합의 원소를 순회하기 위한 Iterator를 반환합니다.
toArray()	집합의 모든 원소를 배열로 반환합니다.
clone()	집합의 얕은 복사본을 반환합니다.

출력

Iterator 사용

        Iterator<int[]> iter = set.iterator();
        while (iter.hasNext()) {
            int[] arr = iter.next();
            System.out.println(Arrays.toString(arr));
        }

for-each 사용

        for (String element : set) {
            System.out.println(element);
        }

---

LinkedHashSet

🥕 중복 불허: 모든 Set 인터페이스의 구현체처럼 LinkedHashSet도 중복된 원소를 허용하지 않습니다.

🥕 삽입 순서 유지: LinkedHashSet은 원소들이 추가된 순서를 유지합니다. 이것은 내부적으로 연결 리스트를 사용하여 구현됩니다.

🥕 빠른 검색: 해시 테이블을 사용하기 때문에 원소의 검색이 빠르다.

🥕 Null 원소: LinkedHashSet은 null 원소를 하나만 허용합니다.

🥕 다양한 집합 연산: Set 인터페이스를 구현하므로, 합집합, 교집합, 차집합과 같은 기본 집합 연산을 지원합니다.

🥕 순회: 원소를 삽입 순서대로 순회할 수 있습니다. 이는 일반적인 HashSet과는 다르게, 순서가 보장됩니다.

시간 복잡도

• 삽입: ${O(1)}$
• 삭제: ${O(1)}$
• 검색: ${O(1)}$

공간 복잡도

${O(n)}$

출력

        // LinkedHashSet 생성
        LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();

        // 원소 추가
        linkedHashSet.add("Apple");
        linkedHashSet.add("Banana");
        linkedHashSet.add("Cherry");
        linkedHashSet.add("Date");
        linkedHashSet.add("Elderberry");

        // 원소 출력 (삽입 순서대로 출력됨)
        for (String element : linkedHashSet) {
            System.out.println(element);
        }

---

TreeSet

🍕 정렬된 데이터: TreeSet은 원소를 정렬된 순서로 저장합니다. 자연 순서나 커스텀 Comparator에 따른 순서를 사용할 수 있습니다.

🍕 중복 불허: TreeSet은 집합이므로 중복된 원소를 허용하지 않습니다.

🍕 균형 이진 검색 트리: 내부적으로 레드-블랙 트리(Red-Black Tree)와 같은 균형 이진 검색 트리를 사용하여 데이터를 저장합니다.

🍕 다양한 집합 연산: TreeSet은 Set 인터페이스를 구현하기 때문에 집합 연산(교집합, 합집합, 차집합 등)을 기본적으로 지원합니다.

🍕 Null 원소: 기본적으로 TreeSet은 null 값을 허용하지 않습니다.

🍕 순회 가능: 원소를 정렬된 순서로 순회할 수 있습니다.

시간 복잡도

삽입 : ${O(logn)}$
삭제 : ${O(logn)}$
검색 : ${O(logn)}$

공간 복잡도

${O(n)}$

메소드

메소드	설명
add(E e)	원소를 추가합니다. 성공하면 true, 이미 존재하면 false를 반환합니다.
remove(Object o)	지정한 원소를 제거합니다. 성공하면 true, 원소가 존재하지 않으면 false를 반환합니다.
clear()	모든 원소를 제거합니다.
contains(Object o)	지정한 원소가 존재하면 true, 그렇지 않으면 false를 반환합니다.
first()	가장 작은 원소를 반환합니다.
last()	가장 큰 원소를 반환합니다.
lower(E e)	지정한 원소보다 작은 가장 큰 원소를 반환합니다.
higher(E e)	지정한 원소보다 큰 가장 작은 원소를 반환합니다.
pollFirst()	가장 작은 원소를 제거하고 반환합니다.
pollLast()	가장 큰 원소를 제거하고 반환합니다.
size()	저장된 원소의 개수를 반환합니다.
isEmpty()	TreeSet이 비어있으면 true, 그렇지 않으면 false를 반환합니다.

집합 연산 메소드는 동일

출력

        Iterator<int[]> iter = set.iterator();
        while (iter.hasNext()) {
            int[] arr = iter.next();
            System.out.println(Arrays.toString(arr));
        }

TreeSet에서의 정렬

TreeSet은 정렬이 되는 Set이므로 정렬 순서를 지정해줘야 할 때가 있다.

배열 -> 배열을 사전순에서 역순으로 정렬해야 할 때

java

        TreeSet<int[]> set = new TreeSet<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                for (int i = 0; i < arr1.length; i++) {
                    if (arr1[i] != arr2[i]) {
                        return Integer.compare(arr2[i], arr1[i]);
                    }
                }
                return 0;
            }
        });


        set.add(new int[]{3, 4, 1, 2});
        set.add(new int[]{1, 2, 3, 4});
        set.add(new int[]{2, 3, 4, 1});
        set.add(new int[]{1, 2, 3, 5}); 

        // [3, 4, 1, 2]
        // [2, 3, 4, 1]
        // [1, 2, 3, 5]
        // [1, 2, 3, 4]

kotlin

    val set: TreeSet<IntArray> = TreeSet { arr1, arr2 ->
        val len1 = arr1.size
        val len2 = arr2.size
        val minLen = minOf(len1, len2)

        for (i in 0 until minLen) {
            if (arr1[i] != arr2[i]) {
                return@TreeSet arr1[i] - arr2[i]
            }
        }

        return@TreeSet len1 - len2
    }


    set.add(intArrayOf(1, 2))
    set.add(intArrayOf(1, 1))
    set.add(intArrayOf(1, 32))
    set.add(intArrayOf(11, 32))
    set.add(intArrayOf(9, 12))
    set.add(intArrayOf(41, 456))
    set.add(intArrayOf(541, 23))
    set.add(intArrayOf(31, 52))
    set.add(intArrayOf(15, 689))
    
    
    //[1, 1]
    //[1, 2]
    //[1, 32]
    //[9, 12]
    //[11, 32]
    //[15, 689]
    //[31, 52]
    //[41, 456]
    //[541, 23]

객체 -> 객체의 특정 조건에 따라 정렬해야 할 때,

import java.util.Comparator;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Comparator<Person> comparator = new Comparator<Person>() {
            @Override
            public int compare(Person p1, Person p2) {
                return p1.age - p2.age;  // 나이를 기준으로 오름차순 정렬
            }
        };

        TreeSet<Person> set = new TreeSet<>(comparator);

        set.add(new Person(30, "Alice"));
        set.add(new Person(25, "Bob"));
        set.add(new Person(35, "Charlie"));

        for (Person p : set) {
            System.out.println(p);
        }
    }
}

class Person {
    int age;
    String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return name + ": " + age;
    }
}