셋(Set)

셋(Set)은 해시테이블(HashTable)을 통해 구현되어지기 때문에 추가, 삭제, 검색에 대한 성능도 해시테이블과 동일 ( 평균적으로 O(c) )하다.

문제는 면접때 셋이 뭐할때 쓴느건가요? 라고 물어보면 십중팔구는 특정 키가 있는지 없는지 검사할때 사용한다고 대답한다.

이렇게 대답하는 사람들은 대부분 셋을 실무에서 키가 있는지 없는지 유무를 검사하는 경우만 했을 가능성이 크다.

사실 맞는 말이기도 하고 실무에서 셋을  키 우뮤를 판단하는데 많이 사용하기 때문에 자연스럽게 나오는 대답이다.

 

import java.util.HashSet;
import java.util.Set;
 
 
public class Main {
    
    public static void main(String[] args)   {
 
 
        Set<String> set = new HashSet<>();
        set.add("java");
        set.add("C++");
 
        System.out.println(set.contains("java")); // true
        System.out.println(set.contains("python")); // false
        System.out.println(set.contains("C++")); // true
    }
 
}

 

위 코드는 셋에 java, C++ 을 원소로 넣고 해당 집합에 원소들이 포함되어 있는지 확인하는 코드이다.

하지만 셋은 정확히 따지고 보면 단순히 키값 유무를 판단하라고만 있는 것이 아니다.

셋은 영어로 Set 이고 번역하면 수학적 용어로 집합이다.

수학적인 용어로 집합을 바라봐야 정말 셋의 자료구조를 잘 파악하고 있는 것이다.

 

위키백과에서 셋을 다음과 같이 설명하고 있다.

컴퓨터 과학에서, 집합이란 특정한 값들을 저장하는 자료구조이다.
이때, 값들을 순서가 존재하지 않으며 중복되지 않는다.
이는 수학에서의 유한집합의 컴퓨터 구현이다.
다른 모음(Collection) 타입에서 특정 원소를 검색하는것이 주 업무인 반면, 집합은 대상 원소가 집합에 소속되었는지 여부를 검사한다  

집합은 대상원소가 집합에 소속되어 있는지 여부를 검사한다고 했는데 셋의 자료구조는 하나의 단일 집합에서만 사용될 때 보다 다른 집합과 함께 무언가를 검사 할 때 더 유용한 자료구조이다.

 

요즘은 중학교 때 배우는지 잘 모르겠지만 예전 고등학교  수학정석1 젤 첫 번째 chapter 가 집합에 대해서 나온다.

 

셋은 수학적으로 위 이미지와 같은 밴 다이어그램을 표현하기위한 자료구조라고 생각하는게 더 도움이 된다.

예를들어 w-shingling 알고리즘은  두 문서간 유사도를 검사할때 적용할수 있는 알고리즘중 하나이다.

문서 A 와 문서 B의 유사도 알고리즘은 아래 공식과 같다. 

이것을 풀기 위해 셋의 자료구조를 이용해야 하는 것이다. 

위 공식을 보면 셋 자료구조가 단순히 키값이 있는지 없는지 우무를 판단하는 작은 개념보다 수학적으로 생각하고 풀어야 한다는 느낌이 들지 않는가 ?

 

어쨌든 ... 근데 문제는 자바에서 셋을 위한 자료구를 위해 HashSet<K>, C++ 에서는 stl::hash_set 을 제공해주는데 

두 집합간의 합집합(union), 교집합(intersection) 차집합(difference) 등으로 메소드명이 보이진 않고 기존 메소드들을 좀 응용해서 구현할수 있다.  Guava 라이브러리를 사용하면 위와 같은 메소드들을 utility 처럼 제공해 주긴하지만 직접 구현해보고 이글을 마무리한다.

 

 
import java.util.HashSet;
import java.util.Set;
 
public class Main {
 
    public static void main(String[] args)   {
 
 
        Set<String> s1 = new HashSet<>();
        s1.add("java");
        s1.add("python");
 
        Set<String> s2 = new HashSet<>();
        s2.add("java");
        s2.add("c++");
 
 
        System.out.println(union(s1, s2));
        System.out.println(intersect(s1, s2));
        System.out.println(difference(s1, s2));
 
    }
 
 
    // 합집합
    public static <E>
    Set<E> union(Set<E> s1, Set<E> s2) {
        Set<E> s = new HashSet<>(s1);
        s.addAll(s2);
        return s;
    }
 
    // 교집합
    public static <E>
    Set<E> intersect(Set<E> s1, Set<E> s2) {
        Set<E> s = new HashSet<>(s1);
        s.retainAll(s2);
        return s;
    }
 
    // 차집합
    public static <E>
    Set<E> difference(Set<E> s1, Set<E> s2) {
        Set<E> s = new HashSet<>(s1);
        s.removeAll(s2);
        return s;
    }
}
 

 

 

레퍼런스

• 위키백과 - 집합