[자료구조] 집합

[자료구조] 집합

2021. 3. 3. 12:21ㆍFront-end/자료구조

728x90

집합(Set 클래스)

개념

집합이란

정렬되지 않은 컬렉션
원소는 반복되지 않음(중복되는 원소가 없음)
수학에 나오는 유한 집합의 개념을 컴퓨터 과학에 적용한 것

수학 시간에 배웠던 집합

집합 - 유일하게 구분되는 원소의 모임

원소는 중괄호 { }로 둘러싼다
예) 자연수의 집합은 1보다 같거나 큰 정수로 구성된다. ( N = {1,2,3,4,5,6,...} )

공집합 (널집합) - 원솨 하나도 없는 집합

예) 24와 29 사이의 소수의 집합은 공집합임(24와 29 중에는 소수가 없기 때문, 소수: 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수)
공집합은 {} 으로 표시

**즉, 집합은 정렬 개념이 없는 원소가 중복되지 않는 배열이라고 볼 수 있음

집합 만들기(Set 객체의 생성)

자바스크립트에는 set 클래스가 내장되어 있다

Set 객체는 Set 생성자 함수로 생성한다.

Set 생성자 함수에 인수를 전달하지 않으면 빈 Set 객체가 생성된다.

const set = new Set();

console.log(set); // Set(0) {}

set 생성자 함수는 이터러블을 인수로 전달받아 Set 객체를 생성한다.

이 때 이터러블의 중복된 값은 Set 객체에 요소로 저장되지 않는다.

(이터러블이란 해당 객체 내 요소들을 하나씩 반복하여 순환 가능한 객체로 배열,문자열,Map,Set은 이터러블임)

const set1 = new Set([1,2,3,3]);

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

const set2 = new Set('hello');

console.log(set2) // Set(4) {"h","e","l","o"}

중복을 허용하지 않는 Set 객체의 특성을 활용하여 배열에서 중복된 요소를 제거할 수 있다.

//원래 배열의 중복 요소를 제거하려면

const uniq = array => array.filter((element,index) => array.indexOf(element) === index);

console.log(uniq([2,1,2,3,4,3,4])); // [2,1,3,4]

//Set을 사용한 배열의 중복 제거

const uniq2 = array => [...new Set(array)];

console.log(uniq2([2,1,2,3,4,3,4])); // [2,1,3,4]

요소 개수 확인(size)

Set객체의 요소 개수를 확인할 때는 size 프로퍼티를 사용한다.

const set3 = new Set([1,2,3,3]);

console.log(set3.size); // 3



//객체 비구조화 할당 문법을 이용해서

const {size} = new Set([1,2,3,3]);

console.log(size); // 3

요소 추가(add)

Set 객체에 요소를 추가할 때는 add 메소드를 사용한다.

const set4 = new Set();

console.log(set4); // Set(0) {}

set4.add(1);

console.log(set4); // Set(1) {1}

add메소드는 새로운 요소가 추가된 Set 객체를 반환하므로 add 메소드를 호출한 후에 add 메소드를 연속적으로 호출 할 수 있다.

const set5 = new Set();

set5.add(1).add(2);

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

Set 객체에 중복된 요소의 추가는 허용되지 않는다. 이 때 에러가 발생하지는 않고 무시된다.

const set6 = new Set();

set6.add(1).add(2).add(2);

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

일치 비교 연산자(===)를 사용하면 NaN과 NaN은 다르다고 평가한다.(NaN은 자신과 일치하지 않는 유일한 값이다)

하지만 Set 객체는 NaN과 NaN을 같다고 평가하여 중복 추가를 허용하지 않는다.

+0과 -0은 일치 비교 연산자 ===dh 마찬가지로 같다고 평가하여 중복 추가를 허용하지 않는다.

const set7 = new Set();

console.log(NaN === NaN); // false

console.log(0 === -0); //true



set7.add(NaN).add(NaN);

console.log(set7); //Set(1) {NaN}



set7.add(0).add(-0);

console.log(set7); //Set(2) {NaN,0}

Set 객체는 객체나 배열과 같이 자바스크립트의 모든 값을 요소로 저장할 수 있다

set8

    .add(1)

    .add('a')

    .add(true)

    .add(undefined)

    .add(null)

    .add({})

    .add([])

    .add(()=>{});

console.log(set8); //Set(8) {1, "a", true, undefined, null, {}, [], ()=>{}}

요소 존재 여부 확인(has)

Set 객체에 특정 요소가 존재하는지 확인하려면 has 메소드를 사용한다.

has 메소드는 특정 요소의 존재 여부를 나타내는 boolean 값을 반환한다.

(값이 있으면 true, 값이 없으면 false)

const set9 = new Set([1,2,3]);

console.log(set9.has(2)); //true

console.log(set9.has(4)); //false

요소 삭제(delete)

Set 객체의 특정 요소를 삭제하려면 delete 메소드를 사용한다.

delete 메소드는 삭제 여부를 나타내는 boolean 값을 반환한다.

delete 메소드에는 인덱스가 아니라 삭제하려는 요소값을 인수로 전달해야 한다.

Set 객체에는 순서에 의미가 없기 때문에, 즉 배열과 같이 인덱스를 가지지 않기 때문이다.

const set10 = new Set([1,2,3]);

set10.delete(2);

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

set10.delete(1);

console.log(set10); // Set(1) {3}

만약 존재하지 않는 값을 삭제하려하면 에러 없이 무시된다.

const set11 = new Set([1,2,3]);

set11.delete(0);

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

delete 메소드는 삭제 성공 여부를 나타내는 boolean 값을 반환하기 때문에 add 메소드와 달리 연속적으로 호출할 수 없다.

요소 일괄 삭제(clear)

Set 객체의 모든 요소를 일괄 삭제하려면 clear 메소드를 사용한다.

clear 메소드는 언제나 undefined를 반환한다.

const set12 = new Set([1,2,3]);

set12.clear();

console.log(set12); // Set(0) {}

요소 순회(forEach, for..Of)

Set 객체의 요소를 순회하려면 forEach 메소드를 사용한다.

array의 forEach 메소드와 유사하게 콜백함수와 콜백함수 내부에서 this로 사용될 객체를 인수로 전달한다. 이 때 콜백함수는 다음과 같이 3개의 인수를 전달받는다.

첫번째 인수: 현재 순회 중인 요소 값(element)
두번째 인수: 현재 순회 중인 요소 값(element)
세번째 인수: 현재 순회 중인 Set 객체 자체

첫번째 인수와 두 번째 인수는 같은 값이다. 이 처럼 동작하는 이유는 array의 forEach 메소드와 인터페이스를 통일하기 위해서 이며 다른 의미는 없다.(array의 forEach함수는 element,index,array 순이었는데, Set 객체는 순서에 의미가 없으므로 인덱스를 안가지기 때문)

const set13 = new Set([1,2,3]);

set13.forEach((v,v2,set) => console.log(v,v2,set));

/*

1 1 Set(3) {1,2,3}

2 2 Set(3) {1,2,3}

3 3 Set(3) {1,2,3}

*/

Set객체는 이터러블이다. 따라서 for … of 문으로 순회할 수 있으며 스프레드 문법과 배열 디스트럭처링 (비구조화 할당) 의 대상이 될 수 있다.

(스프레드 문법 : 스프레드 연산자(…) - 배열,문자열,객체 등 반복 가능한 객체(이터러블)를 개별 요소로 분리할 수 있는 것)

const set14 = new Set([1,2,3]);

for(let value of set14){

    console.log(value); //1,2,3

} 



const [a, ... rest] = set14;

console.log(a, rest); //1, [2,3]

Set 객체는 요소의 순서에 의미를 갖지는 않지만 Set 객체를 순회하는 순서는 요소가 추가된 순서를 따른다. 다른 이터러블의 순회와 호환성을 유지하기 위해서 이다.

집합 연산(교집합, 합집합, 차집합)

1.교집합(집합A와 집합B의 공통 요소로 구성)

Set.prototype.intersection = function(set){

    const result = new Set();

    for(let value of set){

        if(this.has(value))

            result.add(value);

    }

    return result;

};

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

const setB = new Set([2,4]);

console.log(setA.intersection(setB)); // Set(2) {2,4}

2. 합집합(집합A와 집합B의 중복 없는 모든 요소로 구성)

Set.prototype.union = function(set){

    const result = new Set(this);

    for(let value of set){

        result.add(value);

    }

    return result;

}

const setC = new Set([1,2,3,4,5]);

const setD = new Set([4,6]);

console.log(setC.union(setD)); //Set(6) {1,2,3,4,5,6}

또는 이렇게도 구현 가능하다.(더 간단)

Set.prototype.union = function(set){

    return new Set([...this,...set]);

}

3. 차집합 (A-B는 A에는 존재하지만 B에는 존재하지 않는 요소)

Set.prototype.difference = function(set){

    let result = new Set(this);

    for(let value of set){

        result.delete(value);

    }

    return result;

}

const setE = new Set([1,2,3,4]);

const setF = new Set([2,4]);

console.log(setE.difference(setF)); //Set(2) {1,3}

console.log(setF.difference(setE)); //Set(0) {}

4. 부분집합

: 집합 A가 집합 B에 포함되는 경우, 집합 A는 집합 B의 부분집합, 집합B는 집합A의 상위집합이다.

4-1) 상위집합

Set.prototype.isSuperset = function(set){

    //상위집합이려면 부분집합의 원소를 다 가지고 있어야 함

    for(let value of set){

        if(!this.has(value))

        return false;

    }

    return true;

}

const setG = new Set([1,2,3,4]);

const setH = new Set([2,4]);

// setG가 setH의 상위집합인지를 묻고 있다.

console.log(setG.isSuperset(setH)); // true

4-2) 부분집합

Set.prototype.isSubset = function(set){

// 부분집합이라면 상위집합이 부분집합의 원소를 다 가지고 있어야 한다

    for(let value of this){

        if(!set.has(value))

            return false;

    }

    return true;

}

const setI = new Set([2,4]);

const setJ = new Set([1,2,3,4]);

//setI가 setJ의 부분집합인지를 묻고 있다.

console.log(setI.isSubset(setJ)); //true

//setJ가 setI의 부분집합인지를 묻고 있다 

console.log(setJ.isSubset(setI)); //false