et - 06

이 내용은 'Learning JavaScript Data Structures and Algorithms'(로이아니 그로네르 저, 이일웅 역) 책의 내용을 제 생각과 함께 정리한 글입니다.

틀린 내용 혹은 수정이 필요한 내용이 있다면 말씀해주시면 감사하겠습니다.

5장까지 순차(sequential) 자료 구조인 배열, 스택, 큐, 연결 리스트를 공부했다. 6장의 주제는 집합(Set) 자료구조다. - 집합보다는 Set이라고 부르는게 더 적합할 것 같아서 Set이라고 부르겠다.

• Set은 정렬되지 않은(unordered) 컬렉션으로 중복된 원소가 없다.

• 이는 수학책에 나오는 유한 집합(finite set)의 개념을 컴퓨터 과학에 적용한 것이다.

Set 구현하기

• 지금부터 살펴볼 Set 클래스는 ECMAScript 6 명세에 근거한 것임을 밝혀둔다.

function Set() {
   var items = {}; 
}  

• '배열이 아닌, 객체로 집합(원소)을 표현한다'는 사실이 중요하다.

• JS의 객체는 동일한 키로 여러 프로퍼티를 가질 수 없으므로 Set에서 원소가 중복되지 않는 특성이 그대로 보장된다.

• 다음은 Set 클래스에서 구현할 메소드들이다. (ECMAScipt 6 Set 클래스를 모방한 것이다.)

• add(item): 원소 추가

• remove(item): 원소 삭제

• has(item): 원소 포함 여부 확인

• clear(): 모든 원소 삭제

• size(): 원소 개수 반환

• showValues(): Set의 모든 원소를 배열 형태로 구현한다.

has(value)

this.has = function (value) {
    return value in items;
    // return items.hasOwnProperty(value)
    // 이 방법이 상속받은 객체의 프로퍼티는 확인하지 않고
    // 대상 객체 고유의 프로퍼티만 확인하므로 더 권장된다.
  };

add(value)

this.add = function (value) {
    // value가 이미 Set에 포함되어 있는 확인 필요
    if (!this.has(value)) {
      items[value] = value; // 키와 값을 동일하게 저장하는 이유는 나중에 편하라고. 딱히 이유는 없다.
      return true;
    }
    return false;
  };

remove(value), clear()

remove

 this.remove = function (value) {
    if (this.has(value)) {
      delete items[value];
      return true;
    }
    return false;
  };

clear

this.clear = function () {
    items = {};
  };

• 빈 객체를 할당해 초기화한다. loop 돌면서 지우는 것보다 낫다.

size()

  // 첫 번째 방법
   this.size = function () {
    return Object.keys(items).length;
  };

  // 두 번째 방법
   this.size = function () {
    let count = 0;
    for (let prop in items) {
      if (items.hasOwnProperty(prop)) ++count;
    }
    return count;
  };

values(), showValues()

values

this.values = function () {
    return Object.values(items);
  };

showValues

// 화면에 현재 Set의 상태를 보여주기 위한 용도
this.showValues = function () {
    return console.log(Object.values(items));
  };

Set 클래스 사용

const set = new Set();
set.add(1);
set.showValues(); // ["1"]
console.log(set.has(1)); // true
console.log(set.size()); // 1

set.add(2);
set.showValues(); // ["1", "2"]
console.log(set.has(2)); // true
console.log(set.size()); // 2

set.remove(1);
set.showValues(); // ["2"]

set.remove(2);
set.showValues(); // []

집합 연산

• 집합에서 사용 가능한 연산은 4가지가 있다.

• 합집합 / 교집합 / 차집합 / 부분집합

합집합

• Set 클래스에 union메소드(합집합)를 다음과 같이 구성하자.

  this.union = function (otherSet) {
    const unionSet = new Set();
    var values = this.values();

    for (let i = 0; i < values.length; i++) unionSet.add(values[i]);

    var values = otherSet.values();
    for (let i = 0; i < values.length; i++) unionSet.add(values[i]);

    return unionSet;
  };


const set = new Set();
set.add(1);
set.add(2);
set.add(3);

const set2 = new Set();
set.add(3);
set.add(4);
set.add(5);
set.add(6);

let unionAB = set.union(set2);
console.log(unionAB.values()); // 1,2,3,4,5,6

교집합

• 교집합에 대한 설명은 생략하겠다.

  this.intersection = function (otherSet) {
    let intersectionSet = new Set();
    var values = this.values();

    for (let i = 0; i < values.length; i++) {
      // 두 집합에 서로 겹치는 원소가 있는지 찾아준다.
      if (otherSet.has(values[i])) intersectionSet.add(values[i]);
    }

    return intersectionSet;
  };

차집합

• ex) A,B 두 집합이 있을 때 A에는 속하지만 B에는 속하지 않는 원소 x의 집합을 의미한다.

  // difference
  this.difference = function (otherSet) {
    const differenceSet = new Set();

    let values = this.values();
    for (let i = 0; i < values.length; i++) {
      if (!otherSet.has(values[i])) differenceSet.add(values[i]);
    }
    return differenceSet;
  };

부분집합

• ex) 원소 A의 모든 원소는 반드시 B에 존재해야 함을 의미한다.

this.subset = function (otherSet) {
    if (this.size() > otherSet.size()) return false;
    else {
      let values = this.values();
      for (let i = 0; i < values.length; i++) {
        if (!otherSet.has(values[i])) return false;
      }
      return true;
    }
  };