자료구조 - 집합

집합

1. 개요

집합이란 명확한 조건을 만족하는 자료의 모임을 의미.

다른 집합에 포함된 집합은 부분집합 또는 진부분집합 이라고 한다.

2. 배열로 집합 만들기

같은 자료형이 모인 집합은 배열로 표현할 수 있다.

배열로 집합 만들기

모든 요소가 같은 자료형으로 구성된 집합은 배열로 표현할 수 있다. 예를 들어 정수로 이루어진 {1,2,3,4,5,6,7,8} 은 요소의 개수가 8개인 int형 배열 안에 넣을 수 있다.

그런데 배열을 사용하여 집합을 표현하려면 집합의 요소 개수와 배열의 요소 개수는 항상 같아야 한다. 즉, 집합의 상태를 표현할 데이터가 필요하다. 따라서 다음과 같이 집합을 표현하는 배열과 이 배열의 정보(집합의 최대 크기, 집합의 요소 개수)를 담은 클래스를 함께 사용해야 한다.

class IntSet {
    int max;	// 집합의 최대 크기
    int num;	// 집합의 요소 개수. 공집할일 경우 0
    int[] set;	// 집합 본체
}

3. 집합 클래스 구현 예제

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

    // 생성자
    public IntSet(int capacity) {
        num = 0;
        max = capacity;
        try {
            set = new int[max];
        } catch (OutOfMemoryError e) {
            max = 0;
        }
    }

    // 집합의 최대 개수
    public int capacity() {
        return max;
    }

    // 집합의 요소 개수
    public int size() {
        return num;
    }

    // 집합에서 n을 검색 (index 반환)
    public int indexOf(int n) {
        for (int i = 0; i < num; i++) {
            if (set[i] == n) return i;
        }
        return -1;
    }

    // 집합에 n이 있는지 없는지 확인
    public boolean contains(int n) {
        return indexOf(n) != -1;
    }

    // 집합에 n을 추가
    public boolean add(int n) {
        // 가득 찼거나 이미 n이 존재하면
        if (num >= max || contains(n)) return false;
        else {
            set[num++] = n; // 가장 마지막 자리에 추가
        }
        return true;
    }

    // 집합에서 n을 삭제
    public boolean remove(int n) {
        int idx; // n이 저장된 요소의 인덱스
        // 비어있거나 n이 존재하지 않을 경우
        if (num <= 0 || (idx = indexOf(n)) == -1) return false;
        else {
            set[idx] = set[--num]; // 마지막 요소를 삭제한 곳으로 이동
            return true;
        }
    }

    // 집합 s에 복사
    // 원본은 자기 자신(this)이고 복사 대상은 s
    // 최대 요소 개수가 차이날 경우 복사 대상 s의 크기에 맞춤
    public void copyTo(IntSet s) {
        int n = (s.max < num) ? s.max : num; // 복사할 요소 개수
        for (int i = 0; i < n; i++) {
            s.set[i] = set[i];
        }
        s.num = n;
    }

    // 집합 s를 복사
    public void copyFrom(IntSet s) {
        int n = (max < s.num) ? max : s.num; // 복사할 요소 개수
        for (int i = 0; i < n; i++) {
            set[i] = s.set[i];
        }
        num = n;
    }

    // 집합 s와 같은지 확인
    public boolean equalTo(IntSet s) {
        if (num != s.num) return false; // 요소의 개수가 같지 않으면 다른 집합
        for (int i = 0; i < num; i++) {
            int j = 0;
            for (; j < s.num; j++) {
                // 정렬되어있지 않기 때문에 다른 값이 나올 경우로 따지면 안됨.
                if (set[i] == s.set[j]) break;
            }
            if (j == s.num) { // set[i] 는 s에 포함되지 않는다.
                return false;
            }
        }
        return true;
    }

    // 집합 s1과 s2의 합집합을 복사
    public void unionOf(IntSet s1, IntSet s2) {
        copyFrom(s1);                           // 집합 s1을 복사
        for (int i = 0; i < s2.num; i++) {      // 집합 s2의 요소를 추가
            add(s2.set[i]);
        }
    }

    //  "{ a b c }" 형식의 문자열로 표현 바꿈
    public String toString() {
        StringBuilder temp = new StringBuilder("{ ");
        for (int i = 0; i < num; i++) {
            temp.append(set[i]).append(" ");
        }
        temp.append("}");
        return temp.toString();
    }
    
        // 공집합인지 확인
    public boolean isEmpty() {
        return size() == 0;
    }

    // 집합이 가득 찼는지 확인
    public boolean isFull() {
        return capacity() == size();
    }

    // 집합 초기화
    public void clear() {
        set = new int[capacity()];
    }

    // 집합 s와의 합집합 구하기
    public boolean add(IntSet s) {
        int size = size();
        for (int i = 0; i < s.size(); i++) {
            add(s.set[i]);
        }
        return size != size();
    }

    // 집합 s와의 교집합 구하기
    public boolean retain(IntSet s) {
        boolean flag = false;
        for (int i = 0; i < s.size(); i++) {
            if (!s.contains(set[i])) {
                flag = remove(set[i]);
            }
        }
        return flag;
    }

    // 집합 s와의 차집합 구하기
    public boolean remove(IntSet s) {
        boolean flag = false;
        for (int i = 0; i < s.size(); i++) {
            flag = remove(s.set[i]);
        }
        return flag;
    }
}

• 출처 : 자료구조와 함께 배우는 알고리즘 입문(자바편) - 이지스 퍼블리싱