집합(Set)

Stack, Queue, linked List 같은 자료구조들은 순차(Sequential) 자료구조다.

집합(Set)은 정렬되지 않은(unordered)컬렉션으로 원소는 반복되지 않는다.(중복허용 x)

 

ES6에서 Set이 추가되었다.

Set을 한번 직접 만들어보고 필요한 기능도 추가해보자.

 

this.items는 원소가 들어갈 객체,

this.index는 원소가 들어갈 다음위치(마지막index + 1).

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

has메서드는 해당 value값을 가지고 있는지 여부 판단

    has(value) {
        let keys = Object.keys(this.items);
        for (let i in keys) {
            if (this.items[i] === value) return true;
        }
        return false;
    }

add메서드는 가지고 있지않으면 원소를 넣어주는 기능

add(value) {
	if (!(this.has(value))) {
		this.items[this.index++] = value;
        return true;
    }
	return false;
}

remove메서드는 가지고 있으면 제거

    remove(value) {
        let isDeleted = false;
        Object.keys(this.items).forEach((elem,i) => {
            if(this.items[elem]=== value){
                delete this.items[i];
                isDeleted = true;
            }
        });
        return isDeleted;
    }

clear()메서드는 삭제후 초기화

clear() {
        this.items = {};
        return true;
    }

size() 메서드는 들어간 원소의 숫자

    size() {
        return Object.keys(this.items).length;
    }

values()메서드는 현재 원소들의 배열을 반환

values(){
        const sortedKeys = this.entries();

        return sortedKeys.map((val, i)=>{
            return this.items[i];
        })
    }

keys()메서드는 key값(여기서는 index)을 반환

 

종합하면

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

    add(value) {
        if (!(this.has(value))) {
            this.items[this.index++] = value;
            return true;
        }
        return false;
    }

    remove(value) {
        let isDeleted = false;
        Object.keys(this.items).forEach((elem,i) => {
            if(this.items[elem]=== value){
                delete this.items[i];
                isDeleted = true;
            }
        });
        return isDeleted;
    }

    keys() {
        const keys = Object.keys(this.items).map((val) => {
            return parseInt(val, 10);
        })
        return keys.sort((a, b) => a - b )
    }

    values(){
        const sortedKeys = this.entries();

        return sortedKeys.map((val, i)=>{
            return this.items[i];
        })
    }

    has(value) {
        let keys = Object.keys(this.items);
        for (let i in keys) {
            if (this.items[i] === value) return true;
        }
        return false;
    }

    clear() {
        this.items = {};
        return true;
    }

    size() {
        return Object.keys(this.items).length;
    }
}

const set1 = new Set();
set1.add(1);
set1.add(2);
set1.add(3);
console.log(set1.values());  // [ 1, 2, 3 ]
console.log(set1.remove(2)); // true
console.log(set1.size());    // 2 

합집합

    union(otherSet){
        const unionSet = new Set();
        
        for(let val of this.values()){
            unionSet.add(val);
        }

        for(let val of otherSet.values()){
            unionSet.add(val);
        }

        return unionSet;
    }

교집합

intersection(otherSet){
        const intersectionAB = new Set();

        for(let val of this.values()){
            if(otherSet.has(val)){
                intersectionAB.add(val);
            }
        }

        return intersectionAB;
    }

차집합

    difference(otherSet){
        var differenceAB = new Set();

        for(let val of this.values()){
            if(!otherSet.has(val)){
                differenceAB.add(val);
            }
        }
        return differenceAB;
    }

부분집합

    subset(otherSet){
        if(this.size() > otherSet.size()){
            return false;
        }else{
            const values = this.values();
            for(let val of values){
                if(!otherSet.has(val)) return false;
            }
            return true;
        }
    }

실행해보면

const set1 = new Set();
set1.add(1);
set1.add(2);
set1.add(3);

const set2 = new Set();
set2.add(4);
set2.add(5);
set2.add(6);

const set3 = set1.union(set2);
console.log(set3.values());     // [1, 2, 3, 4, 5, 6]
const set4 = set3.intersection(set1);
console.log(set4.values());     // [1, 2, 3]
const set5 = set3.difference(set1); 
console.log(set5.values());     // [4, 5, 6]

console.log(set1.subset(set3)); // true

 

참고문헌: Learning Javascript Data Structures and Algorithms - 로리아니 그로네르

git repository: https://github.com/taeheongo/Data-Structures-and-ALgorithm