2. 집합

👀  집합?

1. 항목이 유일한지 확인할때 필요한 강력한 자료 구조중 하나.

3. 유한하고 구분되는 객체들의 그룹.(정렬되지 않고 중복되지 않는 항목들의 그룹).

4. 집합은 해시 테이블의 구현을 기초로 하기때문에 O(1)상수 시간에 유일한 항목을 확인하고 추가할 수 있다.

 

🟣 배열과 어떻게 다른가요?

1. 배열은 각 요소가 정수 인덱스를 가지고 있기때문에 순서가 유지되고 중복된 값을 포함할 수 있는 자료 구조

2. Set 객체는 중복되지 않은 고유한 값을 저장하기 때문에 순서가 중요하지 않고 중복된 값은 허용하지 않는다.

 

👀  JS의 Set 객체

js에서는 set(집합)을 기본 지원한다.

var exampleSet = new Set();

기본 set 객체에는 집합 내 항목들의 현재 개수를 나타내는 size 정수 속성 하나만 존재한다.

 

🟣 삽입 [Set.add]

var exampleSet = new Set();
exampleSet.add(1); // exampleSet: Set {1}
exampleSet.add(1); // exampleSet: Set {1}
exampleSet.add(2); // exampleSet: Set {1,2}

1. set은 유일한지 확인하기 때문에 중복되는 항목은 추가할 수 없다.

2. set으로 항목을 삽입하는 것은 상수 시간에 일어나서 시간복잡도 O(1)이다.

 

🟣 삭제 [Set.delete]

var exampleSet = new Set();
exampleSet.add(1); // exampleSet: Set {1}
exampleSet.delete(1); // true
exampleSet.add(2); // exampleSet: Set {2}

1. Set.delete는 boolean을 반환한다.

2. 해당 항목이 존재해서 삭제했으면 true, 존재하지 않아서 삭제에 실패했으면 false

3. 배열에서 항목 하나를 삭제하려면 O(n)의 시간이 걸리는데 set을 이용해 O(1)시간으로 해당하는 항목을 지울 수 있는게 큰 장점.

 

🟣 포함 [Set.has] 

var exampleSet = new Set();
exampleSet.add(1); // exampleSet: Set {1}
exampleSet.has(1); // true
exampleSet.has(2); // false
exampleSet.add(2); // exampleSet: Set {1,2}
exampleSet.has(2); // true

1. 해당 항목이 집합 내에 존재하는지 확인

2. 해당 항목이 존재하면 true, 존재하지 않으면 false

3. 포함도 시간복잡도 O(1)시간이 걸린다.

 

👀  Set 유틸리티 함수

🟣 교집합

function intersectSets (setA, setB) {
    var intersection = new Set();
    for(var elem of setB){ // setB의 elem(순환중의 현재 요소)
    	if(setA.has(elem)){ // setB의 elem가 setA에 포함되어 있다면
            intersection.add(elem); // intersection이름의 Set객체에 포함시켜라
        }
    }
    return intersection;
}

var setA = new Set([1,2,3,4]), setB = new Set([[2,3]);
intersectSets(setA, setB);// Set {2,3}

 

🟣 상위 집합 여부 확인

function isSuperset(setA, subset) {
    for(var elem of subset){
        if(!setA.has(elem)){
            return false;
        }
    }
    return true;
}

var setA = new Set([1,2,3,4]), setB = new Set([2,3]), setC = new Set([5]);

isSuperset(setA,setB); // true
isSuperset(setA,setC); // false

 

🟣 합집합

function unionSet(setA, setB){
    var union = new Set(setA);
    for(var elem of setB){
        union.add(elem);
    }
    return union;
}

var setA = new Set([1,2,3,4]), setB = new Set([2,3]), setC = new Set([5]);

unionSet(setA,setB); // set {1,2,3,4} // 중복하는걸 제외하고 합쳐서 반환
unionSet(setA,setC); // set {1,2,3,4,5} // 중복하는걸 제외하고 합쳐서 반환

 

🟣 차집합

function differenceSet(setA, setB){
    var difference = new Set(setA);
    for(var elem of setB){
        difference.add(elem);
    }
    return difference;
}

var setA = new Set([1,2,3,4]), setB = new Set([2,3]);

differenceSet(setA,setB); // set {1,4} // 중복하는걸 제외하고 반환