셋 (Set)

Set 자료구조에 대해

• Set은 중복을 허용하지 않는 자료구조로, 요소의 집합을 나타냄.
• 주로 데이터의 유일성을 보장하고자 할 때 사용
• 수학적 집합 개념을 따르며, 순서가 중요하지 않은 데이터를 관리할 때 유용
• 해시 테이블을 사용한다고 해서 Hash Set이라고도 불림.

Set의 주요 연산

1. 요소 추가 (Add): Set에 요소를 추가. 중복된 요소는 무시됨.
2. 요소 삭제 (Remove): Set에서 특정 요소를 삭제. 요소가 존재하지 않으면 아무런 동작도 하지 않음.
3. 요소 존재 여부 확인 (Has): Set에 특정 요소가 포함되어 있는지 확인. 포함 true, 그렇지 않으면 false를 반환.
4. 모든 요소 삭제 (Clear): Set의 모든 요소를 삭제.
5. Set 크기 확인 (Size): Set에 포함된 요소의 개수를 반환.
6. Set 순회 (Iteration): Set의 모든 요소를 순회. for...of 루프, forEach 메서드 등을 사용하여 요소를 순회할 수 있음.
7. Set 변환 (Conversion): Set을 배열로 변환하거나, 배열을 Set으로 변환할 수 있음 . Array.from() 메서드나 스프레드 연산자 ...를 사용.

장점

1. 중복 제거: 자동으로 중복 요소를 제거.
2. 빠른 탐색: 해시 테이블을 기반으로 하여 평균적으로 O(1) 시간에 탐색이 가능.
3. 수학적 집합 연산 지원: 합집합, 교집합, 차집합 등의 연산을 효율적으로 지원.

단점

1. 순서가 없음: 요소의 순서가 중요할 때는 부적합.
2. 메모리 사용: 해시 테이블을 사용하므로 리스트보다 메모리를 더 사용할 수 있음.
3. 변경 불가 요소만 가능: 해시 테이블을 사용하므로 가변 객체는 포함할 수 없음.

자바스크립트 예시

class Set {
    constructor() {
        this.items = {};
    }

    // 셋에 원소를 추가합니다.
    add(value) {
        if (!this.has(value)) {
            this.items[value] = value;
            return true;
        }
        return false;
    }

    // 셋에서 원소를 제거합니다.
    remove(value) {
        if (this.has(value)) {
            delete this.items[value];
            return true;
        }
        return false;
    }

    // 셋에 특정 원소가 존재하는지 확인합니다.
    has(value) {
        return this.items.hasOwnProperty(value);
    }

    // 셋의 모든 원소를 배열로 반환합니다.
    values() {
        return Object.values(this.items);
    }

    // 셋의 크기를 반환합니다.
    size() {
        return Object.keys(this.items).length;
    }

    // 셋을 비웁니다.
    clear() {
        this.items = {};
    }

    // 두 셋의 합집합을 반환합니다.
    union(otherSet) {
        const unionSet = new Set();
        this.values().forEach(value => unionSet.add(value));
        otherSet.values().forEach(value => unionSet.add(value));
        return unionSet;
    }

    // 두 셋의 교집합을 반환합니다.
    intersection(otherSet) {
        const intersectionSet = new Set();
        this.values().forEach(value => {
            if (otherSet.has(value)) {
                intersectionSet.add(value);
            }
        });
        return intersectionSet;
    }

    // 두 셋의 차집합을 반환합니다.
    difference(otherSet) {
        const differenceSet = new Set();
        this.values().forEach(value => {
            if (!otherSet.has(value)) {
                differenceSet.add(value);
            }
        });
        return differenceSet;
    }

    // 셋이 다른 셋의 부분집합인지 확인합니다.
    isSubsetOf(otherSet) {
        return this.values().every(value => otherSet.has(value));
    }
}

// 셋 사용 예시
const setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

const setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);
setB.add(5);

console.log(setA.values()); // [1, 2, 3]
console.log(setB.values()); // [2, 3, 4, 5]

console.log(setA.union(setB).values()); // [1, 2, 3, 4, 5]
console.log(setA.intersection(setB).values()); // [2, 3]
console.log(setA.difference(setB).values()); // [1]
console.log(setA.isSubsetOf(setB)); // false

setA.remove(1);
console.log(setA.isSubsetOf(setB)); // true

// 자바스크립트의 set
// Set 객체 생성
const set = new Set();

// 값 추가
set.add(1);
set.add(2);
set.add(3);
set.add(2); // 중복된 값은 무시됩니다.

console.log(set); // Set { 1, 2, 3 }

// 값 제거
set.delete(2);
console.log(set); // Set { 1, 3 }

// 값 확인
console.log(set.has(1)); // true
console.log(set.has(2)); // false

// Set의 크기
console.log(set.size); // 2

// Set의 모든 값 출력
set.forEach(value => console.log(value)); // 1, 3

// Set을 배열로 변환
const setArray = Array.from(set);
console.log(setArray); // [1, 3]

// Set을 비웁니다.
set.clear();
console.log(set); // Set {}

// 합집합, 교집합, 차집합 구현 예시
const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4, 5]);

// 합집합
const union = new Set([...setA, ...setB]);
console.log(union); // Set { 1, 2, 3, 4, 5 }

// 교집합
const intersection = new Set([...setA].filter(x => setB.has(x)));
console.log(intersection); // Set { 2, 3 }

// 차집합
const difference = new Set([...setA].filter(x => !setB.has(x)));
console.log(difference); // Set { 1 }