아주 기초적인 Set (중복을 허용하지 않는 자료구조) 구현 (JAVA)

1. Set 대해

1. 중복을 허용하지 않는 자료구조이다.

2. set 자료구조에 값을 추가시 중복 제거한다

   • 이 경우 Hash를 이용 한다면 시간 복잡도는 O(1)이다.
   • 다른 경우를 사용 한다면 이미 자료구조 내에 구성된 값들을 일일히 확인(선형탐색 또는 이분탐색) 한 뒤 없다면 추가, 있다면 추가하지 않는 방법으로 O(n) 또는 O(log n) 시간 복잡도를 가질 것이다.
   • 여기서는 선형탐색 하는 방법을 제시한다

3. Set 자료 구조의 구현 코드를 보면, 필드에 max와 [] set, num이 존재하며

   • max는 필드인 set의 최대 크기를 말한다.
   • max를 넘어선다면 max * 2 배열을 만들어 배열의 깊은 복사를 한다.
   • set은 데이터가 담길 배열이다.
   • num은 중복이 없는 데이터가 담긴 배열의 길이이다.

4. 그러므로 set 자료구조의 값을 삭제시 num 을 이용하면 된다.

이를 이용한 구현 코드는 바로 아래에 있다.

2. 구현코드

public class Set  {
    private int max;
    private int[] set;
    private int num;


    public Set(int[] array){
        this(array.length);
        for (int i = num; i < max; i++){
           if (!contains(array[i])){
               set[num] = array[i];
               num++;
           }
        }
    }

    public Set(int capacity){
        max = capacity;
        num = 0;
        try {
            set = new int[max];
        }catch (OutOfMemoryError e){
            max = 0;
        }
    }

    // default size is 10
    public Set(){
        max = 10;
        num = 0;
        try {
            set = new int[max];
        }catch (OutOfMemoryError e){
            max = 0;
        }
    }

    public boolean add(int element){
        if (num + 1 == max){
            copyArray();
        }
        if (!contains(element)){
            set[num++] = element;
            return true;
        }
        return false;
    }

    /**
     * remove 는 element 가 set[num - 1] 안에 포함되어 있다면 삭제하는 메서드이기 때문에
     * 해당 element 가 num - 1 부분 즉 끝 부분일 경우와 끝 부분이 아닐 경우로 나뉜다.
     * 왜냐하면 배열의 깊은 복사가 이루어져야 하는데,
     * 해당 element 를 제외하고 복사해야하기 때문이다.
     * 내가 생각하는 방법은
     * 1. 끝 부분이 아닐 경우 element Index 의 바로 다음 인덱스부터 tmp 배열에 넣는다.
     * 2. 끝 부분일 경우 해당 index 를 0으로 초기화 하고, num--를 해준다.
     * @param element
     * @return
     */
    public boolean remove(int element){
        // max size == 0
        if (max == 0) return false;

        if (!contains(element)) return false;

        int index = indexOf(element);
        // num 은 set 의 크기이기 때문이다.
        if (index + 1 < num){
            int[] tmp = new int[max];
            for (int i = 0; i < num; i++){
                if (index == i) tmp[i] = set[++pt];
                else tmp[i] = set[pt];
                pt++;
            }
            num--;
            set = tmp;
        // num 과 같은 경우
        }else {
            set[index] = 0;
            num--;
        }

        return true;
    }

    public void copyArray(){
        max *= 2;
        int[] tmp = new int[max];
        for (int i = 0; i < max; i++){
            tmp[i] = set[i];
        }
        set = tmp;
    }

    public boolean contains(int element){
        return (indexOf(element) != -1) ? true : false;
    }

    public int indexOf(int element){
        for (int i = 0; i < num; i++){
            if (set[i] == element){
                return element;
            }
        }
        return -1;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < num; i++){
            sb.append(set[i] + ",");
        }
        String string = sb.substring(0,sb.length()-1);
        string += "]";
        return string;

    }

    public int getNum() {
        return num;
    }
}

3. 구현을 마치며

• 해당 Set 구현 코드는 primitive int만 가지는 Set 자료구조이므로 향후 Generic, Iterable 적용하여 다시 구현해 볼 예정이다.
• add 의 시간 복잡도, remove 의 시간 복잡도가 O(n) 이다.
• 아주 기본적인 Set 을 구현하려 했으나 copyArray(),remove(),toString() 등의 메서드가 추가 되었지만 그리 깔끔한 코드가 되지 못한 거 같다.