집합 알고리즘 구현

Set을 사용하지 않고 list나 ArrayList, 배열만 가지고 집합을 만들 수 있을까?

여기서 만들어볼 것은

1. 집합 기능 즉, set

2. 합집합

3. 차집합

4. 교집합 

이렇게 4가지를 구할 예정이다.

제일 먼저 해야할것은 값을 어떻게 추가할 것인지 알아야 한다.

Scanner sc = new Scanner(System.in);
int an = sc.nextInt();
		
int[] a = new int[an];

for (int i = 0; i < an; i++) {
	a[i] = sc.nextInt();
}
		
int bn = sc.nextInt();
int[] b = new int[bn];
		
for (int i = 0; i < bn; i++) {
		b[i] = sc.nextInt();
}

즉, a배열과 b배열로 풀기위합니다.

왜 배열로 시작할까요? 상관없지만 이러고 싶었답니다. ㅎㅎ

아무튼

첫번째부터 시작해 보자.

set기능을 만들려면

같은 값이 반복되면 안된다.

그전에 더 쉽게 계산하기 위해 배열을 list로 변환하는 작업을 가졌다.

 List<Integer> tolist(int[] arr) {
	Arrays.sort(arr);
	List<Integer> ne = new ArrayList<>();
	for (int i = 0; i < arr.length; i++) {
		ne.add(arr[i]);
	}
	return ne;
}

간단한 작업이므로 

본론으로 넘어가면

set으로 만드는 작업을 가져야한다.

위에서 같은 값이 나오면 안된다고 했는데

이는 1 1 2 2 라는 숫자가 이 메소드(함수)에 들어오면

1 2로 변환이 되어야 한다.

List<Integer> set(List<Integer> list) {
	List<Integer> setList = new ArrayList<>();
	for (int i = 0; i < list.size(); i++) {
		setList.add(list.get(i));
		for (int j = i+1; j < list.size(); j++) {
			if (setList.contains(list.get(j))) {
				i++;
			}
		}
		
	}
	return setList;
}

하나하나 설명하자면

setList라는 리스트를 생성한다.

그리고 첫번째 for문에서 바로 그 값을 넣는다. 예를 들어

1 1 2 2 라는 값이 들어온다고 가정했을때

현재 setList에는 값에는 1이라는 숫자가 들어오게 된다.

그리고 두번째 for문

i을 1증가 시켜야 한다. 왜냐하면 위치가 같으면 다른 리스트가 아닌 이상 무조건 같은 값이기 때문이다.

그리고 그 값이 존재하는지 확인했다.

만약에 그 값이 존재한다면 i값을 강제로 증가시켜서 setList에 저장이 안 되게 만들어야 한다.

위의 예시를 그대로 가져오면

1 1 2 2

가 처음에는 1이 들어온다.

두번째 for 문에서는 1 2 2 가 반복된다.

1과 일치하는 것이 존재하기 때문에 해당 값에서 넘어간다.

즉, 1의 위치가 0과1인데 위치:1을 넘어갔기때문에

현재 i의 위치는 2가 된다. 그리고 2를 저장시킨다.

그리고 위 방법을 반복 시킨다.

지금 생각한 사실인데 저 식들을 equals로 해도 같은 값이 나올것 같다.

두 번째 합 집합이다. 사실 이 메소드는 생각보다 쉽게 구현했다.

 List<Integer> add(List<Integer> a, List<Integer> b) {
	List<Integer> temp = new ArrayList<>(a);
	temp.addAll(b);
	Collections.sort(temp);
	return temp;
}

물론 이걸 로는 set이 되지는 않는다.

일단 설명부터 하자면

a리스트와 b리스트를 하나의 리스트로 합쳤다.

근데 왜 sort를 할까? 그건 바로 set때문에 하는 행위다.

예를들어 1 2 1 2 라는 값이 있다면 순서대로 존재하지 않을 경우 정상적으로 들어오지 않기 때문에 부득이하게 sort를 하게 되었다.

그리고 나서 위set메소드와 연계하면 된다.

그러면 우리가 원하는 합집합을 구할 수 있게 된다.

 

3. 차집합이다.

이건 동일하면 지운다는 아이디어에서 채택한 방법이다.

 List<Integer> sub(List<Integer> a, List<Integer> b) {
	List<Integer> temp = new ArrayList<>(a);
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
				if(a.get(i).equals(b.get(j))) {
					temp.remove(a.get(i));
				}
		}
	}
	return temp;
}

a리스트와  b리스트를 서로 비교하는데

일치하는게 있으면 다른 값으로 대체하거나 아니면 지우면 된다.

나는 지우는 방법을 선택하였다.

이건 예시를 드는 편이 이해하는데 빠를 것 같다.

만약 a가 1 2 3 5 이고

b가 1 5 라면

일단 temp에 a를 저장시킨다. 저장 시키는 이유는 조금 있다 설명할 예정이다.

처음에는 1과 1이 비교한다.

일치하기 때문에 temp에서 1을 제거한다.

그 다음은 1과 5 일치하지 않기 때문에 넘어간다.

그 다음은 2 근데 애석하게도 2는 제거할 대상이 없다. 왜냐하면 1과 5는 2와 다르기 때문이다.

3도 마찬가지다.

다음은 5 5는 b의 2번째(배열에서는 : 1)랑 일치하기 때문에 지운다.

이렇게 되면 

결론적으로 2와 3만 남게 된다. 그래서 답은 2,3이다.

아, a를 temp에 저장시키는 이유는 만약 일치하지 않는다면 a의 값자체가 차집합이기때문이다.

왜냐하면 뺄것이 없기 때문이다. 

4 교집합

이건 바로 코드를 보여주는 게  나을 것같다. 왜냐하면 차 집합과 하나 빼고 일치한다.

 List<Integer> inter(List<Integer> a, List<Integer> b) {
	List<Integer> temp = new ArrayList<>();
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			if(a.get(i).equals(b.get(j))) {
				temp.add(a.get(i));
			}
		}
	}
		
	return temp;
}

뭐가 달라졌을까?

사실 같은 코드라 봐도 무방하다.

다른점이 있다면 temp에 값이 아무것도 없고 remove가 아니라 add를 시키는 점이 다른 점이다.

물론 2개를 리펙토링해서 비슷하게 만들 수도 있겠지만 그럴 필요가 있을까?

이 4가지를 활용해서 여러가지가 가능하다.

예를들어 여집합

여집합은 그 집합을 제외한 모든 값을 말한다.

일단 여집합을 구하기 위해서는

전체 집합이 필요하다.

add(a,b) 그리고 그 값을 빼고 싶은 집합을 넣어주면 된다.

즉, a의 여집합을 구하고 싶다면

sub(add(a,b),a)  이런 식으로 구하게 되면 된다.

 

물론 집합이 2개만 존재하는 것은 아니다 3~4개도 존재 할 수 도 있다.

이것들의 조합으로 다 가능하다.

a합b합c합d 이렇게 구하면 된다.ㅎㅎ

 

이건 백준 문제가 아니기 때문에 굳이 다른 사람 코드를 볼 필요는 없을 것 같다.