Data Structures & Algorithms with Javascript : Sets

 

[이전 글]2024.07.23 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Hashing

Data Structures & Algorithms with Javascript : Hashing

set은 중복되는 원소(member)가 없고 원소 간에 순서가 없는 집합이다. 
👩🏻‍💻오늘은 내장된 Set()을 한번 직접 클래스로 구현해 보자.

Set의 정의

• 원소가 없는 set은 empty set(공집합)이라고 한다. universe(전체 집합)는 가능한 모든 원소 set을 가리킨다.
• 두 set이 동일한 원소를 지닌다면 서로 같다.
• 하나의 set B가 다른 set A의 원소들을 포함한다면 set A는 set B의 subset(부분 집합)이다.

Set 연산

 

• Union : 두 set의 모든 원소들 (합칩합)
• Intersection : 두 set의 원소들 중공통 원소들 (교집합)
• Difference : 두 set 중 교집합을 제외한 원소들(차집합)

Set 클래스 구현

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

class Set{
	constructor(){
    	this.dataStore = [];
    }
    
    // 이미 있는 원소가 아니라면 원소 추가
    add(data){
    	if (this.dataStore.indexOf(data) < 0) {
        	this.dataStore.push(data);
        	return true; 
        } else {
        	return false;
        }
    }
    
    // 원소 제거
    remove(data){
        let pos = this.dataStore.indexOf(data); 
        if (pos > -1) {
       this.dataStore.splice(pos,1);
            return true; 
        } else {
            return false;
        }
    }
    
    // 원소 보기
    show(){
    	return this.dataStore;
    }
    
    // 원소가 set에 있는 지 확인하는 헬퍼 함수
    contains(data) {
        if (this.dataStore.indexOf(data) > -1) {
        	return true; 
        } else {
        	return false;
    	} 
    }
    
   // 합집합
    union(){
        let tempSet = new Set();
        for (let i = 0; i < this.dataStore.length; ++i) {
            tempSet.add(this.dataStore[i]); 
        }
        for (let i = 0; i < set.dataStore.length; ++i) { 
            if (!tempSet.contains(set.dataStore[i])) {
                tempSet.dataStore.push(set.dataStore[i]); 
            }
        }    
        return tempSet; 
    }
    
    //교집합
    intersect(set){
        let tempSet = new Set();
        for(let i=0; i< this.dataStore.length; ++i){
            if(set.contains(this.dataStore[i])){
                tempSet.add(this.dataStore[i]);
            }
        }
        return tempSet;
    }

    // set의 크기
    size() {
        return this.dataStore.length;
    }
        
    //부분집합
     subset(set){
        if (this.size() > set.size()) {
            return false; 
        } else {
            return this.dataStore.every(member=>
                set.contains(member)
            )
        }
        
    }

    // 차집합
    difference(set){
        let tempSet = new Set();
        for(let i = 0; i < this.dataStore.length; ++i){
            if(!set.contains(this.dataStore[i])){
                tempSet.add(this.dataStore[i]);
            }
        }
        return tempSet;
    
    }
}

const print = item => console.log(item);

const set1 = new Set();
set1.add("Mike"); 
set1.add("Clayton"); 
set1.add("Jennifer"); 
set1.add("Raymond");

print(set1.show());


const set2 = new Set();

set2.add("Raymond");
set2.add("Cynthia");
set2.add("Bryan");

print(set2.show()); // ['Raymond', 'Cynthia', 'Bryan']


const intersection = set1.intersect(set2);
print(`intersection: ${intersection.show()}`); // intersection: Raymond

const setA = new Set();

setA.add("Cynthia"); setA.add("Clayton"); setA.add("Jennifer"); setA.add("Danny"); setA.add("Jonathan"); setA.add("Terrill"); setA.add("Raymond"); setA.add("Mike");

print(set1.show()); // ['Mike', 'Clayton', 'Jennifer', 'Raymond']
const setB = new Set();

setB.add("Cynthia"); 
setB.add("Raymond"); 
setB.add("Jonathan");

if (setB.subset(setA)) {
   print("setB is a subset of setA.");
} else {
    print("setB is not a subset of setA.");
}
// setB is a subset of setA.

setB.add("Shirley"); // add Shirley to setB
print("add Shirley to setB"); // setB is not a subset of setA.

if (setB.subset(setA)) {
   print("setB is a subset of setA.");
} else {
    print("setB is not a subset of setA.");
}

const difference = setA.difference(setB);
print(`setA[${setA.show()}] difference setB[${setB.show()}] -> ${difference.show()}`);


// setA[Cynthia,Clayton,Jennifer,Danny,Jonathan,Terrill,Raymond,Mike] difference setB[Cynthia,Raymond,Jonathan,Shirley] -> Clayton,Jennifer,Danny,Terrill,Mike

---

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9