셋 (Set)

배열 [1, 2, 3, 2, 4, 1, 5]에서 중복을 제거하고 싶다고 생각해보자.
일일이 확인하며 중복을 찾는 것보다, 중복을 자동으로 허용하지 않는 자료구조가 있다면 훨씬 편리할 것이다.

이것이 바로 셋(Set)의 핵심 개념이다.

 

Set

Set은 데이터의 중복을 허용하지 않는 자료구조이다.

 

내부적으로는 일반적으로 해시 테이블을 기반으로 구현되며, 각 요소는 key만 존재하고 value가 없는 형태로 저장된다.

이 때문에 **해시 셋(HashSet)**이라고도 부르며, 요소 자체가 key의 역할을 수행한다.

Set vs Hash Table

	Hash Table	Set
저장 형태	key-value 쌍	key만 (value 없음)
중복 허용	key 중복 불가	요소 중복 불가
주 용도	데이터 매핑	중복 제거, 존재 여부 확인
예시	{ 1: "이운재", 21: "박지성" }	{ 1, 21, 5 }

 

Set의 핵심 연산

셋은 다음과 같은 기본 연산을 제공한다.

1. add(): 셋에 데이터 추가 (중복이면 무시)
2. isContain(): 셋에 특정 데이터가 있는지 확인
3. remove(): 셋에서 데이터 제거
4. clear(): 셋의 모든 데이터 제거
5. isEmpty(): 셋이 비어있는지 확인

 

Hash Table로 Set 구현하기

Set은 내부적으로 해시 테이블을 사용하되, value는 의미 없는 더미 값(-1)으로 저장한다. 중요한 것은 key의 존재 여부이기 때문이다.

HashSet 클래스

import { HashTable } from "../hash_table/HashTable.mjs";

class HashSet {
  constructor() {
    this.hashTable = new HashTable();  // 내부적으로 해시 테이블 사용
  }
}

 

주요 메서드

1. add() - 데이터 추가

add(data) {
  if (this.hashTable.get(data) == null) {
    this.hashTable.set(data, -1);  // value는 의미 없는 -1
  }
}

 

데이터가 없을 때만 추가한다. 이미 존재하면 무시하여 중복을 방지한다.

예를 들어, add (1)을 두 번 호출해도 1은 한 번만 저장된다.

 

2. isContain() - 데이터 존재 여부 확인

isContain(data) {
  return this.hashTable.get(data) != null;
}

해시 테이블에서 데이터를 조회하여 존재 여부를 반환한다. O(1)의 빠른 검색이 가능하다.

 

3. remove() - 데이터 제거

remove(data) {
  this.hashTable.remove(data);
}

해시 테이블에서 데이터를 제거한다. 

 

4. clear() - 모든 데이터 제거

clear() {
  for (let i = 0; i < this.hashTable.arr.length; i++) {
    this.hashTable.arr[i].clear();  // 각 버킷의 연결 리스트를 비움
  }
}

해시 테이블의 모든 버킷을 순회하며 데이터를 제거한다. 

 

5. isEmpty() - 비어있는지 확인

isEmpty() {
  let isEmpty = true;
  for (let i = 0; i < this.hashTable.arr.length; i++) {
    if (this.hashTable.arr[i].count > 0) {
      isEmpty = false;
      break;
    }
  }
  return isEmpty;
}

모든 버킷을 확인하여 데이터가 하나라도 있으면 false를 반환한다. 

 

6. printAll() - 모든 데이터 출력

printAll() {
  for (let i = 0; i < this.hashTable.arr.length; i++) {
    let currentNode = this.hashTable.arr[i].head;
    while (currentNode != null) {
      console.log(currentNode.data.key);  // key만 출력
      currentNode = currentNode.next;
    }
  }
}

 

Set 사용 예제

let hashSet = new HashSet();

console.log(`isEmpty: ${hashSet.isEmpty()}`);  // isEmpty: true

// 데이터 추가
hashSet.add(1);
hashSet.add(1);    // 중복 - 무시됨
hashSet.add(123);
hashSet.add(512);

hashSet.printAll();  // 1, 512, 123 출력 (순서는 해시 함수에 따라 다름)
console.log(`isEmpty: ${hashSet.isEmpty()}`);  // isEmpty: false

// 데이터 존재 여부 확인
console.log(`isContain: ${hashSet.isContain(1)}`);  // isContain: true

// 데이터 제거
hashSet.remove(1);
hashSet.printAll();  // 512, 123 출력
console.log(`isContain: ${hashSet.isContain(1)}`);  // isContain: false

// 모든 데이터 제거
hashSet.clear();
console.log(`isEmpty: ${hashSet.isEmpty()}`);  // isEmpty: true

주목할 점은 add (1)을 두 번 호출했지만, 출력에는 1이 한 번만 나타난다는 것이다.

 

Set의 시간복잡도

해시 테이블 기반 셋의 시간복잡도는 다음과 같다.

	평균	최악
추가 (add)	O(1)	O(n)
조회 (isContain)	O(1)	O(n)
삭제 (remove)	O(1)	O(n)

• 평균: 해시 함수가 데이터를 골고루 분산시키면 O(1)
• 최악: 해시 충돌로 모든 데이터가 한 버킷에 몰리면 O(n)

 

Set의 실제 활용 사례

1. 중복 제거

배열이나 리스트에서 중복된 요소를 제거할 때 사용한다.

function removeDuplicates(arr) {
  const set = new HashSet();
  const result = [];
  
  for (let item of arr) {
    if (!set.isContain(item)) {
      set.add(item);
      result.push(item);
    }
  }
  
  return result;
}

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

 

2. 존재 여부 빠른 확인

대량의 데이터에서 특정 값의 존재 여부를 빠르게 확인할 때 사용한다.

const visitedPages = new HashSet();

function hasVisited(pageId) {
  return visitedPages.isContain(pageId);
}

function markVisited(pageId) {
  visitedPages.add(pageId);
}

markVisited(101);
markVisited(205);

console.log(hasVisited(101));  // true
console.log(hasVisited(999));  // false

 

3. 집합 연산

두 집합의 합집합, 교집합, 차집합을 구할 때 사용한다.

// 합집합 (Union)
function union(setA, setB) {
  const result = new HashSet();
  // setA의 모든 요소 추가
  // setB의 모든 요소 추가
  return result;
}

// 교집합 (Intersection)
function intersection(setA, setB) {
  const result = new HashSet();
  // setA의 요소 중 setB에도 있는 요소만 추가
  return result;
}

// 차집합 (Difference)
function difference(setA, setB) {
  const result = new HashSet();
  // setA의 요소 중 setB에 없는 요소만 추가
  return result;
}

 

4. 고유한 값 추적

게임에서 수집한 아이템, 방문한 도시, 완료한 퉤스트 등 고유한 값을 추적할 때 사용한다.

const collectedItems = new HashSet();

function collectItem(itemId) {
  if (!collectedItems.isContain(itemId)) {
    collectedItems.add(itemId);
    console.log(`새로운 아이템 ${itemId} 획득!`);
    return true;
  }
  console.log("이미 가지고 있는 아이템입니다.");
  return false;
}

collectItem("sword_01");    // 새로운 아이템 sword_01 획득!
collectItem("shield_02");   // 새로운 아이템 shield_02 획득!
collectItem("sword_01");    // 이미 가지고 있는 아이템입니다.

 

5. 그래프 알고리즘에서 방문 노드 추적

DFS, BFS 같은 그래프 탐색 알고리즘에서 이미 방문한 노드를 추적할 때 사용한다.

function DFS(startNode) {
  const visited = new HashSet();
  const stack = [];
  
  stack.push(startNode);
  
  while (stack.length > 0) {
    const node = stack.pop();
    
    if (!visited.isContain(node.id)) {
      visited.add(node.id);
      console.log(`방문: ${node.id}`);
      
      // 인접 노드를 스택에 추가
      for (let neighbor of node.neighbors) {
        if (!visited.isContain(neighbor.id)) {
          stack.push(neighbor);
        }
      }
    }
  }
}

 

셋은 중복을 허용하지 않는 특성 덕분에 데이터의 유일성을 보장해야 하는 곳에서 빛을 발하는 자료구조이다. 

배열에서 중복 제거, 방문 여부 확인, 집합 연산 등 다양한 문제를 효율적으로 해결할 수 있고, 해시 테이블 기반으로 구현되어 평균 O(1)의 빠른 성능을 제공한다.