[자바스크립트] 집합(Set) 다루기

Javascript

자바스크립트는 기본적으로 집합(Set) 클래스를 지원한다.

Set

자바스크립트에서 집합(Set)이란 중학교 때 처음 배우는 바로 그 집합 개념이다. 이를 일반화해서 얘기하면 유한하고 구분되는 항목들의 그룹이라고 표현할 수 있다. 좀 더 엄밀히 얘기하자면 중복을 허용하지 않고 정렬되지 않은 항목들을 그룹이다. 따라서 정의에 맞게 그 용도 역시 항목의 유일성을 확인하는 것이다.

 

생성

let set1 = new Set([1,2,3])
let set2 = new Set('123')
console.log(set1)
console.log(set2)

집합 생성

Set 객체의 생성자를 이용해서 집합을 생성할 수 있다. 이때 인자로는 iterable(배열, 맵, 집합, 문자열 등)을 받는다. set1은 배열을 이용하여, set2는 문자열을 이용하여 집합을 생성했다. 인자를 넣지 않으면 크기가 0인 빈 집합이 생성된다.

 

삽입/삭제

let set1 = new Set([1,2,3])
set1.add(3) //{1,2,3}
set1.add(4) //{1,2,3,4}
set1.delete(4) //{1,2,3} && return true
set1.delete(4) //{1,2,3} && return false

console.log(set1)

집합 원소에 대해 add() 메소드를 이용해서 삽입을, delete() 메소드를 이용해서 삭제를 진행할 수 있다. delete() 메소드는 삭제의 성공 여부를 boolean으로 반환한다. 이때 삽입과 삭제의 시간복잡도는 O(1)인데, 자바스크립트 집합의 구현이 해시테이블에 근간을 두고 있는 덕분이다.

 

포함여부 확인

let set1 = new Set([1,2,3])
set1.has(1) //true
set1.has(4) //fasle

has() 메소드를 이용해서 포함 여부를 손쉽게 확인할 수 있다. 역시 O(1) 시간 안에 수행된다.

---

위에서 알아본 집합 클래스의 기본 기능들을 가지고 조금 더 응용된 집합 연산을 구현할 수도 있다.

 

교집합

function interSectSets(setA, setB){
  var intersection = new Set()
  setB.forEach(e=>{
    if(setA.has(e)) intersection.add(e)
  })
  return intersection
}

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

console.log(interSectSets(setA, setB)) //Intersection: {2,3}

교집합

하나의 집합에 대해 모든 원소를 탐색하면서 나머지 집합이 해당 원소를 가졌는지 체크해주면 된다. 새로운 집합을 하나 만들어두고 공통 요소로 판명된 것들을 여기에 차곡차곡 넣어서 반환하면 그게 바로 교집합일 것이다.

 

합집합

function unionSet(setA, setB){
  let union = new Set(setA)
  setB.forEach(e=>{
    union.add(e)
  })
  return union
}

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

console.log(unionSet(setA,setB)) //{1,2,3,4,5}

합집합

하나의 집합에다가 나머지 집합의 모든 원소를 하나씩 추가해주면 된다. 집합 자체의 성질에 의해 중복이 걸러지므로 안심하고 추가해주어도 된다.

 

차집합

function differenceSet(setA, setB){
  let difference = new Set(setA)
  setB.forEach(e=>{
    difference.delete(e)
  })
  return difference
}

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

console.log(differenceSet(setA,setB)) //{1}
console.log(differenceSet(setB,setA)) //{4,5}

차집합

합집합의 add() 메소드를 차집합에서는 delete()로 바꾸어주면 된다. 원리는 동일하다. 한가지 주의할점은 A U B 와 B U A 는 결과가 동일하지만 A - B 와 B- A 는 서로 다르다는 점이다. 덧셈은 순서가 바뀌어도 무방하지만 뺄셈에서는 순서가 절대적으로 중요한 것과 같은 이치이다. 따라서 함수를 사용할 때 인자의 순서에 신경을 써주어야 할 것이다.

 

부분집합

function isSubSet(superSet, setA){
  let result = true
  setA.forEach(e=>{
    if(!superSet.has(e)) 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(isSubSet(setA, setB)) //false
console.log(isSubSet(setA, setC)) //true

부분집합

어떤 집합의 모든 원소를 다른 집합이 원소로 갖고 있을 경우 부분집합 관계가 성립한다. 위 그림에서 집합 A의 모든 원소를 집합 B가 갖고 있으므로 A는 B의 부분집합인 것이다. 부분집합 여부를 확인하려면 어떤 집합의 모든 요소를 그 상위 집합이 빠짐없이 포함하고 있는지 확인해주면 된다. 단 하나라도 포함하지 않는다면 부분집합은 성립하지 않는다.