[Java/구현] 집합

집합(Set)

• 특정 조건에 맞는 원소들의 모임
• 집합 표현 방법
  • 원소나열법 : A = { 1, 2, 3, 4, 5 }
  • 조건제시법 : A = { A|A는 정수, 0<A<6 }
  • 벤 다이어그램자바에서는 주로 집합에 HashSet을 사용한다

Java로 표현

1. HashSet - java에서 집합으로 사용

HashSet<Integer> a = new HashSet<>();
a.add(1);
a.add(1);
a.add(3);
a.add(1);
System.out.println(a);  //[1, 3]

2. 직접구현

class MadeSet{ 
    ArrayList<Integer> list; 
    //기본생성자 
    MadeSet(){ 
    this.list = new ArrayList<Integer>(); 
    } 

    //원소 한개받고 처리 
    MadeSet(int a){ 
    this.list = new ArrayList<Integer>(a);
    list.add(a); 
    } 
    //배열받아 생성자 
    MadeSet(int[] arr){
    this.list = new ArrayList<Integer>(); 
    for(int a : arr){ 
        list.add(a); 
        }
    }
    //집합 원소 추가 
    public void add(int x){ 
    for(int a : this.list){ 
        if(item == x){
            return; // 같은값이 있으면 바로 탈출 
        } 
   }
   this.list.add(x); 
   }
}

교집합

• 두 집합이 공통으로 포함하는 원소로 이루어진 집합
  → A∩B
• HashSet a = new HashSet<>();

Java로 표현

1. HashSet 교집합_set

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));  
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

a.retainAll(b);  
System.out.println(a);

 

2. 직접구현

//위(집합 직접구현)와 이어집니다

public MadeSet retainAll(MadeSet listB){  
MadeSet result = new MadeSet();  
    for(int a : this.list){  
        for(int b : listB.list){  
            if(a==b){  
                result.add(a);  
            }  
        }  
    }  
    return result;  
}

합집합

어느 하나의 집합에라도 속하는 원소들을 모두 모은 집합
→ A∪B

Java로 표현

1. HashSet -합집합_set

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));  
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

a.addAll(b);  
System.out.println(a);

2. 직접구현

public MadeSet addAll(MadeSet listB){
	MadeSet result = new MadeSet();
	for(int a : this.list){
		result.add(a);
	}
	for(int b : listB){
		result.add(b);
	}
	return result;
}

차집합

특정한 하나의 집합(A)에만 속하는 원소들의 집합  
→ A - B

Java로 표현
1. HashSet - 차집합 set

HashSet a = new HashSet(Arrays.asList(1,2,3,4,5));
HashSet b = new HashSet(Arrays.asList(2,4,6,8,10));

a.removeAll(b);
System.out.println(a);

 

2. 직접구현 (A-B)

public MadeSet removeAll(MadeSet listB){
	MadeSet result = new MadeSet();
	for(int a : this.list){
		boolean cun = false;
		for(int b : listB){
			if(a==b){
				cun =true;
				break;
			}
		}
		if(!cun){
			result.add(a);
		}
	}
return result;
}

 

여집합

전체집합(U) 중 특정 집단의 원소가 아닌 것들의 집합
→ U - A → A^c or A' (차집합으로 구현가능)