알고리즘(algorithm)feat.JAVA - 집합(Set)

자바(Java)의 알고리즘 중에 집합에 대해 알아보도록 하자.

1) 교집합 - 집합 A와 집합 B의 공통된 부분(=AnB)
2) 합집합 - 집합 A와 집합 B의 모든 부분 (=AuB)
3) 차집합 - 집합 A에서 집합 B와 공통된 부분을 제외시킨 부분(=A-B,A-(AnB))

1. HashSet을 이용해서 나타내기

public class Main {
    public static void main(String[] args) {
    
    //교집합
    //집합 A와 B 선언
    HashSet A = new HashSet(Arrays.asList(1,2,3,4,5)); // 집합 A 선언
    HashSet B = new HashSet(Arrays.asList(2,4,6,8,10)); // 집합 B 선언
    A.retainAll(B);
    System.out.println("교집합 : " + A);
    System.out.println("===구분선===");
    
    //합집합
    //집합 C와 D 선언
    HashSet C = new HashSet(Arrays.asList(1,2,3,4,5)); // 집합 C 선언
    HashSet D = new HashSet(Arrays.asList(2,4,6,8,10)); // 집합 D 선언
    C.addAll(D);
    System.out.println("합집합 : " + C);
    System.out.println("===구분선===");
    
    //차집합
    //집합 E와 F 선언
    HashSet E = new HashSet(Arrays.asList(1,2,3,4,5)); // 집합 E 선언
    HashSet F = new HashSet(Arrays.asList(2,4,6,8,10)); // 집합 F 선언
    E.removeAll(F);
    System.out.println("차집합 : " + E);
    }
    //결과값
    교집합 : [2,4]
    ===구분선===
    합집합 : [1,2,3,4,5,6,8,10]
    ===구분선===
    차집합 : [1,3,5]

2. HashSet이용하지 않고 나타내기

class MySet {
	ArrayList<Integer> list;
    
    //생성자 1
    MySet() {
    	this.list = new ArrayList<Integer>();
    }
    //생성자 2
    MySet(int[] arr) {
    	this.list = new ArrayList<Integer>();
        
        for (int items : arr) {
        	this.list.add(items);
        }
    }
    
    //원소 추가하기(중복 x = HashSet처럼 추가하기)
    public void add(int a) {
    	for (int item : this.list) {
        	//추가하려는 a가 이미 list에 있다면 return시킨다.
            if (item == x) {
            	return;
            }
            //추가하려는 a가 list에 없다면 list에 추가한다.
            this.list.add(a);
        }
    }
    
    //교집합
    public MySet retainAll(MySet b) {
    	//결과를 담을 객체 생성
    	MySet result = new MySet();
    	for (int itemA : this.list) {
        	for (int itemB : b.list) {
            	//주어진 list와 비교될 b를 비교 했을 때 같다면 result에 추가한다.
                if (itemA == itemB) {
                	result.add(itemA);
                } 
            }
        }
        return result;
    }
    
    //합집합
    public MySet addAll (MySet b) {}
    	//결과를 답을 객체 생성
        MySet result = new MySet();
        //여기서 add메서드는 위에 add메서드이다. 즉, 중복된 원소가 발견된다면 1개만 add시켜준다.
        //주어진 list의 모든 원소를 result에 담는다.
        for (int itemA : this.list) {
        	result.add(itemA);
        }
        //b의 모든 원소를 result에 담는다.
        for (int itemA : b.list) {
        	result.add(itemB);
        }
        return result;
    }
    //차집합
    public MySet removeAll(MySet b) {
    	//결과를 담을 객체 생성
        MySet result = new MySet();
        for (int itemA : this.list) {
        	//list에 있는 원소와 b에 있는 원소가 같은지 판별하는 변수
            boolean isSame = false;
            for (int itemB : b.list) {
            	//list에 있는 itemA와 b에 있는 itemB가 같다면 
                //isSame을 true 값으로 바꿔주고 b.list를 순회하는 반복문은 break시켜준다.
            	if (itemA == itemB) {
                	isSame = true;
                    break;
                }
                //isSame이 false라면, 즉, itemA가 itemB와 다르다면 추가한다.
                if(!isSame) {
                	result.add(itemA);
                }
            }
        }
        return result;
    }
}
class Main {
	public static void main(String[] args) {
    	//비교할 두 집합 객체 생성
        MySet a = new MySet();
        MySet b = new MySet();
        
        //위에서 add메서드를 원소가 중복되어 추가된다면, 더이상 추가시키지 않도록 했다.
       	a.add(1);
       	a.add(1);
       	a.add(1);
        System.out.println(a.list);
    	System.out.println("===구분선===");
        a.add(2);
        a.add(3);
        System.out.println(a.list);
    	System.out.println("===구분선===");
        
        //a,b 원소 설정
        a = new MySet(new int[]{1,2,3,4,5});
    	b = new MySet(new int[]{2,4,6,8,10});
        System.out.println("집합 a : " + a);
        System.out.println("집합 b : " + b);
    	System.out.println("===구분선===");
        
        //교집합
        MySet result = a.retainAll(b);
        System.out.println("교집합 : " + a);
    	System.out.println("===구분선===");
        //합집합
        result = a.addAll(b);
        System.out.println("합집합 : " + a);
    	System.out.println("===구분선===");
        //차집합
        result = a.removeAll(b);
        System.out.println("차집합 : " + a);
    	System.out.println("===구분선===");
    }
}
//결과값
[1]
===구분선===
[1,2,3]
===구분선===
a : [1,2,3,4,5]
b : [2,4,6,8,10]
===구분선===
교집합 : [2,4]
===구분선===
합집합 : [1,2,3,4,5,6,8,10]
===구분선===
차집합 : [1,3,5]