[집합 ADT] 부분집합인지 검사하기, 합집합&교집합 구하는 프로그램

문제1 : 두 개의 집합 A와 B를 입력 받아, A가 B의 부분집합인지를 검사하는 프로그램을 작성하시오.

 

입력: 프로그램은 두 개의 집합 A, B를 차례로 표준입력 받는다.

출력: A ⊂ B이면 0을 출력하고, 그렇지 않으면 집합 B에 속하지 않은 집합 A의 가장 작은 원소를 표준 출력한다.

모든 집합은 헤더 노드가 없는 단일연결리스트(singly-inked list) 형태로 구축되어야 한다.

 

입력 예시 1	출력 예시 1
3 ↦ 집합 A 크기 4 6 13 ↦ 집합 A 6 ↦ 집합 B 크기 1 3 4 6 8 13 ↦ 집합 B	0 ↦ A ⊂ B

입력 예시 2	출력 예시 2
3 ↦ 집합 A 크기 7 10 53 ↦ 집합 A 4 ↦ 집합 B 크기 7 10 15 45 ↦ 집합 B	53 ↦ A ⊄ B

 

코드:

#include <stdio.h>
#include <stdlib.h>

typedef struct node {//단일연결리스트 노드
	int data;
	struct node* next;
}node;

void addset(node *set, int e){//  집합에 원소 e추가
	node* newelem = (node*)malloc(sizeof(node));// 노드 추가
	newelem->data = e;// 노드가 가리키는 데이터에 원소 e를 넣어줌
	newelem->next=NULL;// 다음 노드에 NULL값 넣어주기

	while (set->next != NULL) {// 집합set 끝 노드까지 반복
		set = set->next;
	}
	set->next = newelem;// 제일 끝에 새노드 추가
}

int subset(node *A, node *B) {// 부분집합인지 검사하기
	if (A == NULL)// 집합A가 공집합이면 0리턴(공집합은 모든집합의 부분집합)
		return 0;
	else {// 공집합이 아니면
		while (A != NULL) {// A가 NULL값이 나올 때까지
			if (B == NULL) {// B가 비어있으면
				return A->data;// A원소중 가장 적은 원소 출력
			}
			else if (A->data < B->data)// A원소가 B원소보다 작으면 이미 부분집합일 수가 없는 거임
				return A->data;// 그럼  B집합에 포함되지 않는 A집합 원소중 가장 작은 값 출력
			else if (A->data > B->data)// A가 B보다 크면 B를 다음노드로 넘겨
				B = B->next;
			else {// A원소랑 B원소랑 같으면
				A = A->next;
				B = B->next;// 둘다 하나씩 다음노드로 넘겨주삼
			}
		}
		return 0;// 다돌고 다오면 부분집합인 것이므로 0을 반환해줘
	}
}

void freeset(node *set) {// 집합 해제~
	node* p = set;// 임의의 노드 p를 하나선언해서 set을 넣어줘

	while (p != NULL) {// p가 null값이 나올 때까지
		set = set->next;// set은 다음 노드로 넘기고
		free(p);//p를 해제해줘
		p = set;// 다음 노드로 넘어간 set을 p에 넣어줘
	}
}

int main() {
	int size, e;
	node* A = (node*)malloc(sizeof(node));
	node* B = (node*)malloc(sizeof(node));//집합 노드 선언
	A->data = NULL;
	B->data = NULL;// 노드가 가리키는 데이터에 널값 넣어주삼
	A->next = NULL;
	B->next = NULL;// 다음 노드를 가리킬 때도 널값 넣어주삼

	scanf("%d", &size);// A집합 사이즈 받고
	for (int i = 0; i < size; i++) {
		(scanf("%d", &e));// 원소도 받고
		addset(A, e);// 함수 불러서 집합에 원소 추가
	}

	scanf("%d", &size);// B집합 사이즈 받고
	for (int i = 0; i < size; i++) {
		(scanf("%d", &e));
		addset(B, e);// 함수 불러서 집합에 원소 추가
	}
	printf("%d", subset(A, B));
	free(A);
	free(B);

	return 0;
}

 

 

문제2: 두 개의 집합을 입력받아, 합집합과 교집합을 구하는 프로그램을 작성하시오.

 

프로그램은 두 개의 집합 A, B를 차례로 표준입력 받는다.

출력: 각 연산 결과는 두 개의 라인으로 표준출력한다. 첫 번째 라인은 합집합을, 두 번째 라인은 교집합을 나타낸다. 이때 공집합은 0로 출력한다.

모든 집합은 헤더(header) 노드가 추가된 단일연결리스트 형태로 구축되어야 한다.

 

입력 예시 1	출력 예시 1
6 ↦ 집합 A 크기 3 7 45 88 99 101 ↦ 집합 A 4 ↦ 집합 B 크기 7 10 15 45 ↦ 집합 B	□3 7 10 15 45 88 99 101 ↦ 합집합 □7 45 ↦ 교집합

입력 예시 3	출력 예시 3
0 ↦ 집합 A 크기 (공집합) 0 ↦ 집합 B 크기 (공집합)	□0 ↦ 합집합 (공집합) □0 ↦ 교집합 (공집합)

 

코드:

#include <stdio.h>
#include<stdlib.h>

typedef struct node {// 노드 구조체 선언
	struct node* next;
	int data;
}node;

void addset(node* set, int elem) {// 집합set에 원소elem 추가
	node* newnode = (node*)malloc(sizeof(node));// 새로운 노드 할당
	newnode->data = elem;
	newnode->next = NULL;// 초기화 해주고

	while (set->next != NULL) {//집합 끝에 노드추가
		set = set->next;
	}
	set->next = newnode;
}

struct node *_union(node* A, node *B) {// 합집합 구하기
	node* first = A;
	node* second = B;

	node* sumset = (node*)malloc(sizeof(node));// 합집합 담을 집합노드
	sumset->data = NULL;
	sumset->next = NULL;// 초기화 해주고

	if ((first->next == NULL) && (second->next == NULL))// 둘다 공집합이면
		return sumset;// 그냥 빈 리스트 반환
	else if (first->next == NULL) {// 첫번째집합이 공집합이라면
		free(sumset);
		return second;// 두번째집합이 합집합이 되는 거임 반환ㄱ
	}
	else if (second->next == NULL) {// 두번째집합이 공집합이면
		free(sumset);
		return first;//엉 첫번째집합이 합집합이 되는겨
	}
	else {
		first = first->next;
		second = second->next;// 둘다 공집합이 아니라면 다음 노드로 연결해주고

		while ((first != NULL) && (second != NULL)) {// 각 집합의 끝까지 돌 것임
			if (first->data < second->data) {// 첫번째집합 원소가 두번째보다 작으면
				addset(sumset, first->data);
				first = first->next;//첫번째부터 합집합집합에 추가하고
			}
			else if (first->data > second->data) {//아니면 반대로 순서대로 저장하려고 일케하는겨
				addset(sumset, second->data);
				second = second->next;
			}
			else {//같은 원소가 있다?
				addset(sumset, first->data);
				first = first->next;// 한번만 추가하면 됨
				second = second->next;
			}
		}
		while (first != NULL) {//근데이제 위에 반복문을 다돌고 나왔는데 첫번째집합에 남은 원소가 있어
			addset(sumset, first->data);
			first = first->next;// 그럼 추가해주면됨
		}
		while (second !=NULL) {// 얘도 똑같이 ㄱㄱ
			addset(sumset, second->data);
			second = second->next;
		}
	}
	return sumset;// 합집합 반환
}

node* intersect(node* A, node* B) {// 이거는 교집합
	node* first = A;
	node* second = B;
	node* intersect = (node*)malloc(sizeof(node));// 교집합 담을 리스트

	intersect->data = NULL;
	intersect->next = NULL;

	if ((first->next == NULL) && (second->next == NULL)) {//둘 다 공집합이면
		return intersect;// 걍 빈 리스트 반환
    }
	else if (first->next == NULL) {// 첫번째만 공집합이어도
		return intersect;// 빈리스트 반환 왜냐믄 교집합이니께
	}
    else if (second->next == NULL) {// 어 얘도 똑같이
		return intersect;
	}
	else {// 둘다 공집합이 아니야
		first = first->next;
		second = second->next;

		while ((first != NULL) && (second != NULL)) {// 둘 중 하나가 끝나면 끝나는 반복문이여
			if (first->data == second->data) {//원소가 같으면
				addset(intersect, first->data);// 둘 중 하나만 추가해
				first = first->next;
				second = second->next;
			}
			else if (first->data < second->data)// 원소가 다르면 적은것부터 순서대로 추가
				first = first->next;
			else if (first->data > second->data)
				second = second->next;
		}
	}
	return intersect;
}

void print(node* set) {// 출력
	node* p = set->next;// 임시로 노드 하나 선언하고 집합 연결
	if (p == NULL)
		printf("0\n");// 그게 근데 빈집합이야 공집합, 그러면 0 반환
	else {
		while (p != NULL) {// 끝까지
			printf(" %d", p->data);// 집합 원소 출력~!
			p = p->next;
		}
		printf("\n");
	}
}

void freeset(node* set) {// 메모리 해제
	node* p = set;
	while (p != NULL) {
		set = set->next;
		free(p);
		p = set;
	}
}

int main() {
	int size, elem;
	node* A = (node*)malloc(sizeof(node));
	node* B = (node*)malloc(sizeof(node));// 집합 할당 먼저해주고
	node* sumset, * intersectset;//얘들은 각각 합집합 교집합 받을 것들
	A->data = NULL;
	A->next = NULL;
	B->data = NULL;
	B->next = NULL;// 초기화 해주기

	scanf("%d", &size);
	for (int i = 0; i < size; i++) {
		scanf("%d", &elem);
		addset(A, elem);// A집합 원소 받아서 집합에 넣기
	}
	scanf("%d", &size);
	for (int i = 0; i < size; i++) {
		scanf("%d", &elem);
		addset(B, elem);// B집합 원소 받아서 집합에 넣기
	}

	sumset = _union(A, B);// 합집합 구하기
	print(sumset);// 출력
	intersectset = intersect(A, B);// 교집합 구하기
	print(intersectset);// 출력
	
	free(A);
	free(B);// 메모리 해제
	free(sumset);
	free(intersectset);

}