[알고리즘]HashSet을 이용한 집합연산(합집합,교집합,차집합) + 프로그래밍적 집합연산

HashSet을 이용해 집합연산 알고리즘을 작성하기 이전에, HashSet은 공통된 데이터가 들어가지 않는다는 점을 기억해주시길 바랍니다.(오히려 좋아)

 

HashSet의 기본 연산

1. HashSet의 데이터 삽입

HashSet hs = new HashSet();
hs.add(1);
hs.add(1);
hs.add(1);

--> hs를 출력하면 동일한 데이터는 삽입이 되지 않으므로, 1이 하나만 존재함

 

2. HashSet의 데이터 삭제

        HashSet hs = new HashSet();
        hs.add(1);
        hs.add(2);
        
        hs.remove(1); //삭제

 

3. HashSet의 데이터 찾기

        HashSet hs = new HashSet();
        hs.add(1);
        hs.add(2);

        hs.remove(1);
        
        System.out.println(hs.contains(1)); //false 반환
        System.out.println(hs.contains(2)); //ture 반환

 

HashSet을 이용한 집합연산

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

//합집합
hs1.addAll(hs2);
System.out.println(hs1); //[1, 2, 3, 4, 5, 6, 8, 10]

//교집합
hs1.retainAll(hs2);
System.out.println(hs1); //[1, 2, 3, 4, 5, 6, 8, 10]

//차집합
hs1.removeAll(hs2);
System.out.println(hs1);

 

HashSet을 알고리즘적 코드로 작성

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

class Myset{
    ArrayList<Integer> list;
  
    Myset(){
        this.list = new ArrayList<Integer>(); //객체 생성
    }

    Myset(int[] arr){
        this.list = new ArrayList<Integer>();

        for(int num : arr){
            this.list.add(num);
        }
    }
    
    //HashSet과 같이 중복처리를 하기 위한 메소드
    public void add(int n){
        for(int num : this.list){
            if(num == n){
                return;
            }
        }
        this.list.add(n);
    }

    //1.교집합
    public Myset retainAll(Myset b){
        Myset result = new Myset();

        for(int ANum : this.list){
            for(int BNum : b.list){
                if(ANum == BNum){
                    result.add(ANum);
                }
            }
        }
        return result;
    }

    //2.합집합
    public Myset addAll(Myset b){
        Myset result = new Myset();

        for(int ANum : this.list){
            result.add(ANum);
        }

        for(int BNum : b.list){
            result.add(BNum);
        }

        return result;
    }

    //3.차집합
    public Myset removeAll(Myset b){
        Myset result = new Myset();

        for(int ANum : this.list){
            boolean chk = false;
            for(int BNum : b.list){
                if(ANum == BNum){
                    chk = true;
                    break;
                }
            }
            if(!chk){
                result.add(ANum);
            }
        }
        return result;
    }
}

public class set {
    public static void main(String[] args) {

        Myset mysetA = new Myset(new int[]{1,2,3,4,5});
        Myset mysetB = new Myset(new int[]{2,4,6,8,10});

        //1.합집합
        Myset addAll = mysetA.addAll(mysetB);
        //System.out.println(addAll.list); //[1, 2, 3, 4, 5, 6, 8, 10]

        2.교집합
        Myset retainAll = mysetA.retainAll(mysetB);
        System.out.println(retainAll.list); //[2, 4]

        //3.차집합
        Myset removeAll = mysetA.removeAll(mysetB);
        System.out.println(removeAll.list); //[1, 3, 5]

    }
}

 

코드는 아래의 깃링크에 올려두었습니다!

1. HashSet을 이용한 집합연산

https://gist.github.com/KimSeulHa/3105e8836b4c4c92c1e8fe7f2e658148

 

2. 알고리즘을 이용한 집합연산

https://gist.github.com/KimSeulHa/9ec1a15c4e6d125f097c1b7c3b8bf171