자바스크립트로 하는 자료구조와 알고리즘(9장) - 집합

집합은 유한하고 구분되는 객체들의 그룹

 

자바스크립트에서는 Set이 기본 지원됨

 

집합 연산

 

삽입

let exampleSet = new Set();
exampleSet.add(1)

중복해서 추가된다면 추가되지 않는다.

 

삭제

let exampleSet = new Set();
exampleSet.add(1)
exampleSet.delete(1)  // true

boolean값을 반환한다. 

 

포함

이역시 boolean값을 반환한다.

has(1) 이런식으로 사용

 

 

 

교집합

function intersectSets (setA, setB) {
  let intersection = new Set();
  for (let elem of setB){
    if(setA.has(elem)){
      intersection.add(elem);
    }
  }
  return intersection;
}

let setA = new Set([1,2,3,4]);
let setB = new Set([2,3]);
console.log(intersectSets(setA, setB));

 

상위 집합 여부 확인

function isSuperset (setA, subset) {
  for (let elem of subset){
    if(!setA.has(elem)){
      return false;
    }
  }
  return true;
}

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

console.log(isSuperset(setA, setB));
console.log(isSuperset(setA, setC));

 

 

합집합

function unionSet (setA, setB) {
  let union = new Set(setA);
  for (let elem of setB){
    union.add(elem);
  }
  return union;
}

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

console.log(unionSet(setA, setB));
console.log(unionSet(setA, setC));

 

 

차집합

 

function differenceSet (setA, setB) {
  let difference = new Set(setA);
  for (let elem of setB){
    difference.delete(elem);
  }
  return difference;
}

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

console.log(differenceSet(setA, setB));

 

연습문제 

 

집합을 사용해 배열의 중복 항목 확인하기

function checkDuplicates(arr) {
  let mySet = new Set(arr);
  return mySet.size < arr.length;
}

console.log(checkDuplicates([1, 1, 2, 3, 4, 5]));
console.log(checkDuplicates([1, 2, 3, 4, 5]));

시간복잡도 : O(n)

 

개별적인 배열들로부터 유일한 값만을 반환하기

 

두배열을 합친 다음 해당 두 배열을 집합으로 변환함으로써 유일한 항목들만을 저장한다. 

그러고 나서 해당 집합을 다시 배열로 변환하면 결과적으로 유일한 값을 가진 배열이 나온다.

function uniqueList(arr1, arr2) {
  let mySet = new Set(arr1.concat(arr2));
  return Array.from(mySet);
}

console.log(uniqueList([1, 1, 2, 2], [2, 3, 4, 5]));
console.log(uniqueList([1, 2], [3, 4, 5]));
console.log(uniqueList([], [2, 2, 3, 4, 5]));

 

시간 복잡도 O(n+m)