집합

집합

- 명확한 조건을 만족하는 자료의 모임

- 객관적으로 범위를 규정한 '어떤 것'의 모임

- 각각의 '어떤 것'을 요소라 함

- 집합에 포함되는 요소는 달라야 함, 가령 {1, 5, 1}과 같은 집합은 있을 수 없다.

- 정수의 집합처럼 요소의 개수가 무한한 집합을 무한 집합이라고 함

- 요소의 개수가 유한한 집합을 유한 집합이라고 함

 

부분집합과 진부분집합

부분 집합

- A = {1, 3} B={1, 3, 5}일 경우, A의 모든 요소가 집합 B의 모든 요소이면, A는 B의 부분집합이고 'A는 B에 포함된다' 고 표기 => A ⊂ B

진부분 집합

집합 A의 모든 요소가 집합 B의 요소이면서 집합 A와 집합 B가 같지 않을때 'A는 B의 진부분집합이다'라 함

합집합

- 집합A와 집합B가운데 적어도 한쪽에 속하는 요소의 집합을 A와 B의 합집합 A ∪ B

차집합

- 집합 A의 요소 가운데 집합 B의 요소를 제외한 요소의 집합을 차집합이라하며 A-B로 표기

교집합

- 집합 A,B 양쪽 모두에 속하는 요소의 집합을 교집합이라고 함 A ∩ B

 

배열로 집합 만들기

package basic;

public class IntSet {
    int max; // 집합의 최대 크기
    int num; // 집합의 요소 개수
    int[] set; /// 집합 본체

    // 생성자
    public IntSet(int capacity){
        num = 0;
        max = capacity;

        try{
            set = new int[max]; // capacity만큼의 max를 가진 배열을 생성한다.
        }catch (OutOfMemoryError e){ // 배열 생성에 실패할 경우
            max = 0;
        }
    }

    // 집합의 최대 크기 반환하는 메서드
    public int capacity(){
        return max;
    }

    // 집합의 요소 개수를 반환하는 메서드
    public int size(){
        return num;
    }

    // 집합에서 n을 검색할 때
    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) ? true : false;
    }

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

    public boolean remove(int n){
        int idx; // n이 저장된 요소의 인덱스

        if(num <= 0 || (idx = indexOf(n)) == -1) // 비어있거나 n이 존재하지 않으면
            return false;
        else{
            set[idx] = set[--num]; // 마지막 요소를 삭제한 곳으로 옮김
            return true;
        }
    }

    // 집합 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)
                return false;
        }

        return true;
    }

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

    // 문자열 출력
    public String toString(){
        StringBuffer temp = new StringBuffer("{ ");
        for(int i = 0; i <num; i++)
            temp.append(set[i] + " ");
        temp.append("}");
        return temp.toString();
    }
}