[집합 adt] 비트벡터 사용해 부분집합 검사하기, 합집합, 교집합 구하는 프로그램 비트벡터로 작성하기

1. 비트벡터 사용해 부분집합 검사하기

 

 

코드:

#include <stdio.h>
#include<string.h>

int subset(unsigned int A, unsigned int B) {// 집합 A가 집합 B의 부분집합인지 검사
	if ((A | B) == B) // A or B가 B라면 A는 B의 부분집합임
    	return 1; // 부분집합이면 1반환
	else
		return 0; // 부분집합이 아니라면 0반환
}

int main() {
	char Aset[100], Bset[100]; // 집합 Aset과 집합 Bset을 char형으로 선언
	int lenA, lenB; // 각 집합의 길이 저장할 변수
	unsigned int A = 0, B = 0; // 음수를 나타낼 필요 없으니까 unsigned 자료형 사용
	
	gets(Aset); //집합 A입력 받고
	lenA = strlen(Aset); // 길이 계산
	if (Aset[0] != '0') {// 공집합이 아니라면
		for (int i = 0; i < lenA; i++) {
			A = A | (1 << (Aset[i] - 'A'));// A에 문자-'A'해준 값을 left shift해줘서 or하기(비트벡터로 바꾸기)
		}
	}

	gets(Bset); //B도 똑같이 받고
	lenB = strlen(Bset);
	if (Bset[0] != '0') {
		for (int i = 0; i < lenB; i++) {
			B = B | (1 << (Bset[i] - 'A'));// 비트벡터 만들어주기
		}
		printf("%d\n", subset(A, B));// 함수 호출해서 부분집합인지 검사하고 출력
	}
	else
		printf("1");// B가 공집합이라면 부분집합으로 보고 출력(근데 A가 부분집합 아닐 때도 생각해줘야되는데 생각안했네 이제보니까)

	return 0;
}

**비트벡터 어케하는지 몰라서 존나 헤맸음........ 비트연산자 공부하자

 

 

2. 합집합, 교집합 구하는 프로그램 비트벡터로 작성하기

 

코드: 

#include <stdio.h>
#include<string.h>

void _union(int bit1[], int bit2[]) {
	int arr[26];

	int cnt1 = 0;
	int cnt2 = 0;
	for (int i = 0; i < 26; i++) {
		if (bit1[i] != 0)
			cnt1++;
	}
	for (int i = 0; i < 26; i++) {
		if (bit2[i] != 0)
			cnt2++;
	}

	if (cnt1 == 0 && cnt2 == 0) {
		printf("0");
	}
	else {
		for (int i = 0; i < 26; i++) {
			if (bit1[i] == 1) {
				arr[i] = 1;
			}
			if (bit2[i] == 1) {
				arr[i] = 1;
			}
		}

		for (int i = 0; i < 26; i++) {
			if (arr[i] == 1) {
				printf("%c", ('A' + i));
			}
		}
	}
}

void intersect(int bit1[], int bit2[]) {
	int arr[26];

	int flag = 0;
	int cnt1 = 0;
	int cnt2 = 0;
	for (int i = 0; i < 26; i++) {
		if (bit1[i] != 0)
			cnt1++;
	}
	for (int i = 0; i < 26; i++) {
		if (bit2[i] != 0)
			cnt2++;
	}

	if (cnt1 == 0 || cnt2 == 0) {
		printf("0");
	}
	else {
		for (int i = 0; i < 26; i++) {
			if (bit1[i] == 1 && bit2[i] == 1) {
				arr[i] = 1;
				flag++;
			}
		}

		if (flag == 0)
			printf("0");
		else {
			for (int i = 0; i < 26; i++) {
				if (arr[i] == 1) {
					printf("%c", ('A' + i));
				}
			}
		}
	}
}

int main() {
	char Aset[100], Bset[100];
	int lenA, lenB;
	int i = 0;
	int bit1[26] = { 0 }, bit2[26] = { 0 };
	
	gets(Aset);
	lenA = strlen(Aset);
	if (Aset[0] != '0') {
		for (int i = 0; i < lenA; i++) {
			bit1[Aset[i] - 'A'] = 1;
		}
	}

	gets(Bset);
	lenB = strlen(Bset);
	if (Bset[0] != '0') {
		for (int i = 0; i < lenB; i++) {
			bit2[Bset[i] - 'A'] = 1;
		}
	}

	_union(bit1, bit2);
	printf("\n");
	intersect(bit1, bit2);

	return 0;
}