set 집합 구현 21.04.20

20 Apr 2021 in Dev on Java Script, Algorithm

set

객체 그룹 (집합 개념)
중복을 허용하지 않음
정렬되지 않음

let set1 = new Set([5,1,2,3,3])

console.log(set1)
// { 5, 1, 2, 3 }
// 정렬 되지 않는다.
// 중복을 제거한다.

let set2 = new Set('1233')

console.log(set2)
// {"1", "2", "3"}
// 문자열도 각각 분리해준다.

set method

.add() : 추가
.delete() : 삭제 (Boolean 값으로 리턴)
.has() : 포함 여부 확인 (Boolean 값으로 리턴)

let set1 = new Set([1,2,3])
set1.add(3) // {1,2,3} // 중복을 허용하지 않으므로
set1.add(-1) // {1,2,3,-1} // 정렬을 하지 않으므로

set1.delete(-1) // true // 포함된 경우
set1.delete(-1) // false // 포함되지 않은 경우

set1.has(1) // true
set1.has(5) // false

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

set 집합 구현 (교집합, 합집합, 차집합, 부분집합)

교집합

function interSectSets (setA, setB) {
    // 빈 set 생성
    const intersection = new Set();
    // setA를 순회
    setA.forEach( el => { 
        // setB가 setA의 각 요소를 가지고 있는 경우
        if(setB.has(el)) {
            // 빈 set에 해당 요소를 추가
            intersection.add(el);
        }
    })
    return intersection;
}

let arr1 = [1,2,3]
let arr2 = [2,3,4,5]

// array - set 화
let set1 = new Set(arr1);
let set2 = new Set(arr2);

interSectSets(set1, set2)
// {2, 3}

합집합

function unionSet(setA, setB) {
    // 새로운 set 생성
    let union = new Set(setA)
    // 순회
    setB.forEach( el => {
        // 요소 추가 (set 특성 상 중복 요소는 추가가 안됨)
        union.add(el);
    })
    return union;
}

let arr1 = [1,2,3]
let arr2 = [2,3,4,5]

// array - set 화
let set1 = new Set(arr1);
let set2 = new Set(arr2);

unionSets(set1, set2)
//  {1, 2, 3, 4, 5}

차집합

// 차집합은 인자의 순서가 중요. B의 차집합을 구하고 싶으면 A와 B의 위치를 바꿔줘야한다.
function diffSet(setA, setB) {
    let diff = new Set(setA)
    setB.forEach(el => {
        diff.delete(el);
    })
    return diff;
}

let arr1 = [1,2,3]
let arr2 = [2,3,4,5]

// array - set 화
let set1 = new Set(arr1);
let set2 = new Set(arr2);
// {1}

부분집합

function subSet(superSet, set) {
    let result = true;
    set.forEach(el => {
        if(!superSet.has(el)) {
            result = false;
        }
    })
    return result;
}

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

console.log(subSet(setA, setB)) //false
console.log(subSet(setA, setC)) //true

위 문제들은 array + for 문으로도 해결 가능하지만 set과 for Each를 사용하는 이유는 무엇일까?

array 대신 set을 사용해야하는 이유

위 문제들은 단순히 array & for 문으로도 해결 할 수 있다.
그러나 값을 추가할 때마다 해당 값이 이미 있는지 확인하고 값을 추가하는 기존 방식은 매우 큰 오버헤드 발생.
10,000개의 요소를 가진 배열에 15개의 요소를 추가하는 데, 요소를 추가하기 전에 추가하려는 값이 배열에 들어있는지 확인해서 중복값은 스킵하는 과정을 추가

for vs for each vs for of vs for in 성능 비교

https://velog.io/@cada/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-for-loop-%EC%86%8D%EB%8F%84-%EB%B9%84%EA%B5%90

결론 부터 말하자면 특별한 상황이 아니라면 forEach를 사용하는게 가장 좋은 선택.

forEach

let start = new Date().getTime();
let arr = Array(10000000).fill().map((_, i) => i);
let sum = 0;
arr.forEach(e => sum += e);
let end = new Date().getTime();

console.log(end - start);

// 1138

for of

let start = new Date().getTime();
let arr = Array(10000000).fill().map((_, i) => i);
let sum = 0;
for(let val of arr) {
    sum += val;
}
let end = new Date().getTime();

console.log(end - start);

// 1317

for loop

let start = new Date().getTime();
let arr = Array(10000000).fill().map((_, i) => i);
let sum = 0;
for(let i=0; i<arr.length; i++) {
  sum += arr[i];
}
let end = new Date().getTime();

console.log(end - start);

// 1806

for in

let start = new Date().getTime();
let arr = Array(10000000).fill().map((_, i) => i);
let sum = 0;
for(let idx in arr) {
    sum += arr[idx];
}
let end = new Date().getTime();

console.log(end - start);

// 7826