[알고리즘] 백준 11723 집합

문제 소개

비트마스킹 문제이다. 비스마스킹이란 각 비트가 0,1 두개로 이루어져 있는 점을 이용해 집합을 표현하는 테크닉이다.
예를들어 1011(2) 이라는 수가 있다고 하자. 이를 10진수로 본다면 11이라는 아무 의미 없는 수이지만, 각 자리수가 집합에 존재하는지 에대한 유무라고 한다면 1,2,4라는 집합에 포함되고 3은 포함되지 않는다고 생각 할 수 있다. 20개의 원소면 2^20승 즉 2.5바이트 내에 모든 데이터를 표현할 수 있다.

소스 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int val = 0;

bool chk(int x) {
	return (val>>(x-1))%2;
}
void change(int x,bool num) {
	if(chk(x) == 1 && num == 0) val -= 1<<(x-1);
	else if(chk(x) == 0 && num == 1) val += 1<<(x-1);
}

int main() {
	int n;
	scanf("%d",&n);
	while(n--) {
		char s[7];
		string str;
		int num;
		scanf("%s",s);
		str = s;
		if(str.compare("all") == 0) {
			val = (1<<21)-1;
			continue;
		}
		else if(str.compare("empty") == 0) {
			val = 0;
			continue;
		}
		scanf("%d",&num);

		if(str.compare("add") == 0) {
			change(num,1);
		}
		else if(str.compare("remove") == 0) {
			change(num,0);
		}
		else if(str.compare("check") == 0) {
			printf("%d\n",chk(num));
		}
		else if(str.compare("toggle") == 0) {
			if(chk(num)) change(num,0);
			else change(num,1);
		}
	}
}