자료 구조(Data Structure) (3) - Set

Set은 array나 list같은 순열 자료 구조이지만 순서가 존재하지 않는다. 

 

Set 특징

- 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조(collection)

- 삽입 순서대로 저장되지 않고, 특정한 순서를 기대할 수 없는 자료구조

- 수정 가능(mutable)

- 동일한 값 여러 번 삽입 불가 (동일 값을 여러번 넣을 경우 하나의 값만 저장됨)

- Fast Lookup(특정 값을 포함하고 있는지 확인)이 필요할 때 주로 사용

 

Set 구조

- Set 저장 순서

 1. 저장할 요소의 값의 hash 값 구하기

 2. 해시값에 해당하는 공간(bucket)에 값 저장

- 저장하고자 하는 값의 해시값에 해당하는 bucket에 값을 저장하기 때문에 순서가 없음 (index도 없음)

- 해시값 기반의 bucket에 저장하여 중복된 값을 저장할 수 없음

- 해시값 기반으로 저장하여 look up이 빠름

   ㅁ Set의 총 길이와 상관없이 단순히 해시값 계산 후 해당 bucket을 확인하면 됨

* Hash: 단방향(one way) 암호화로, 한 번 암호화하면 복호화가 안됨, 실제 값의 길이와 상관없이 일정한 hash값을 가짐

 

Set 사용

- 중복된 값을 골라내야 할 때

- 빠른 look up을 해야 할 때

- 순서는 상관 없을 때

 

Set 관련 메소드

add메소드: set의 특성과 요소 삽입

let mySet = new Set(['a','b','a']);

mySet.add('a');
mySet.add('b');
mySet.add('c');

mySet.forEach((value) => {
	console.log(value);
}); 
// output: 
// a 
// b
// c

 

중복 항목 확인 함수

function isDuplicated(arr) {
    var mySet = new Set(arr);
    return mySet.size < arr.length;
}
console.log('4개', isDuplicated([1,1,2,3])); // output: 4개 true
console.log('3개', isDuplicated([1,2,3]));   // outpus: 3개 false

function uniqueElements(list1, list2) {
    var mySet = new Set(list1.concat(list2));
    return Array.from(mySet);
}

console.log(uniqueElements([1,2,4,5],[2,3,5,6])); // output: [1, 2, 4, 5, 3, 6]

 

union: 교집합 요소 반환하기

Set.prototype.union = function(otherSet) { 
    // 교집될 set의 값을 넣을 Set 생성
    var unionSet = new Set(); 
  
    for (var elem of this) { 
        unionSet.add(elem); 
    } 
  
    for(var elem of otherSet) {
        unionSet.add(elem); 
	}
    
    return unionSet; 
} 
  
// 각기 다른 Set 생성
var set1 = new Set([10, 20, 30, 40, 50]); 
var set2 = new Set([40, 50, 60, 70, 80]);   
  
// union 메소드로 합치기
var unionSet = set1.union(set2); 
console.log(unionSet.values()); // output: {10, 20, 30, 40, 50, 60, 70, 80}

 

insersection: 합집합 요소 반환

Set.prototype.intersection = function(otherSet) { 
    var intersectionSet = new Set(); 
  
    for(var elem of otherSet) { 
        // 만약 다른 Set에 같은 value값이 있다면 intersectionSet에 넣어주기
        if(this.has(elem)) {
            intersectionSet.add(elem);
        }
    } 
	
    return intersectionSet;                 
} 

var set1 = new Set([10, 20, 30, 40, 50]); 
var set2 = new Set([40, 50, 60, 70, 80]);   

var intersectionSet = set1.intersection(set2); 

console.log(intersectionSet.values());  // output: {40, 50}

 

difference: 다른 요소 찾기

Set.prototype.difference = function(otherSet) { 
    var differenceSet = new Set(); 

    for(var elem of this) { 
        // 만약 value값이 없다면, differenceSet에 값 저장하기
        if(!otherSet.has(elem)) 
            differenceSet.add(elem); 
    }
    return differenceSet; 
} 
  
var set1 = new Set([10, 20, 30, 40, 50]); 
var set2 = new Set([40, 50, 60, 70, 80]);   

var differenceSet = set1.difference(set2); 
console.log(differenceSet); // outpu: {10, 20, 30} 

 

[ 참고 ]

1. https://www.geeksforgeeks.org/sets-in-javascript/