Set 자료구조

집합(Set)

• 중복되는 원소가 없는 비선형 구조
• 인덱스로 접근하지 않는다.
• Js 내장 객체가 존재하지만 따로 구현해보려고 한다.

집합(Set)의 연산

• add : 원소 추가, 중복 원소는 추가하지 않는다.
• remove : 특정 원소를 삭제한다.
• clear : 모든 원소 삭제

집합(Set)의 구현

class MySet {
  constructor() {
    this.set = [];
  }
  has(value) {
    return this.set.includes(value);
  }
  add(value) {
    if (!this.has(value)) {
      this.set.push(value);
      // 삽입에 성공했다는 의미로 true를 반환
      return true;
    }
    // 중복 원소가 있어 실패 했을 경우
    return false;
  }
  remove(value) {
    if (this.has(value)) {
      for (let i = 0; i < this.set.length; i++) {
        if (this.set[i] === value) {
          this.set = [...this.set.slice(0, i), ...this.set.slice(i + 1)];
          break;
        }
      }
      return true;
    }
    return false;
  }
  clear() {
    this.set = [];
  }
  size() {
    return this.set.length;
  }
}

const mySet = new MySet();
mySet.add(1);
mySet.add(1); // 무시됨
mySet.add(1); // 무시됨
mySet.add(2);
console.log(mySet);

mySet.clear();
console.log(mySet);

mySet.add(1);
mySet.add(2);
mySet.remove(3); // 없는 값을 제거하면 아무 일도 일어나지 않는다.
mySet.remove(2);
console.log(mySet);

배열의 메서드 없이 구현

class MySet {
  constructor() {
    this.set = [];
    this.length = 0;
  }
  has(value) {
    let flag = 0;
    for (let i = 0; i < this.length; i++) {
      if (this.set[i] === value) {
        flag = 1;
      }
    }
    return flag ? true : false;
  }
  add(value) {
    if (!this.has(value)) {
      this.set[this.length++] = value;
      return true;
    }
    return false;
  }
  remove(value) {
    if (this.has(value)) {
      for (let i = 0; i < this.length; i++) {
        if (this.set[i] === value) {
          this.set = [...this.set.slice(0, i), ...this.set.slice(i + 1)];
          this.length--;
          break;
        }
      }
      return true;
    }
    return false;
  }
  clear() {
    this.set = [];
    this.length = 0;
  }
  size() {
    return this.length;
  }
}