[백준] 11723 집합 / 구현, 비트마스킹 (C++)

문제
비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.
입력
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력
check 연산이 주어질때마다, 결과를 출력한다.

빡구현으로 풀었다.

#include <iostream>
#include <string>
using namespace std;

int arr[21];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		string s;
		int a;

		cin >> s;
		if (s != "all" && s != "empty")
		{
			cin >> a;
		}
		
		if (s == "add")
		{
			if (arr[a] == 0)
			{
				arr[a] = 1;
			}
		}
		else if (s == "remove")
		{
			if (arr[a] > 0)
			{
				arr[a] = 0;
			}
		}
		else if (s == "check")
		{
			if (arr[a] > 0)
			{
				cout << 1 << "\n";
			}
			else
			{
				cout << 0 << "\n";
			}
		}
		else if (s == "toggle")
		{
			if (arr[a] > 0)
			{
				arr[a] = 0;
			}
			else
			{
				arr[a]++;
			}
		}
		else if (s == "all")
		{
			for (int i = 1; i <= 20; i++)
			{
				arr[i] = i;
			}
		}
		else if (s == "empty")
		{
			for (int i = 1; i <= 20; i++)
			{
				arr[i] = 0;
			}
		}
	}

	return 0;
}

하지만 비트마스킹에 대해서 알아보도록 하자.
공집합 S 를 int 형태로 저장한다.
어차피 컴퓨터는 이 수를 2진수로 계산할테니 비트처럼 사용해보자
코드는 이렇다.

#include <iostream>
#include <string>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int S = 0;
	int M;
	cin >> M;

	for (int i = 0; i < M; i++)
	{
		string a;
		int b;
		cin >> a;

		if (a == "add")
		{
			cin >> b;
			// OR 연산을 하면 만약 b번째 자리에 0일 경우 1로 대체되고,
			// 1일 경우에도 그대로 1으로 남는다.
			S = S | (1 << b);
		}
		else if (a == "remove")
		{
			cin >> b;
			// NOT, AND 연산을 사용한다.
			// 한자리 숫자만 들어오기 때문에 가능하다.
			// 예를 들어 b가 2라고 하고 현재 상태가 1111 이라고 가정한다면,
			// 1111 & ~(0100) -> 1111 & 1011 이므로 원래 자리는 그대로 보존되고
			// 1011 이 되어 그 자리만 삭제된다.
			S = S & ~(1 << b);
		}
		else if (a == "check")
		{
			cin >> b;
			// 만약 그 자리에 숫자가 존재한다면
			// AND 연산을 했을 때 0이 아닌 어떤 수가 나오게 되는 것을 이용
			if (S & (1 << b))
			{
				cout << "1\n";
			}
			else
			{
				cout << "0\n";
			}
		}
		else if (a == "toggle")
		{
			cin >> b;

			if (S & (1 << b))
			{
				// remove 작업
				S &= ~(1 << b);
			}
			else
			{
				// add 작업
				S |= (1 << b);
			}
		}
		else if (a == "all")
		{
			// all은 1~20의 위치가 전부 1이어야 한다.
			// 단순하게 표현하기 위해서 21까지 밀고, 1을 빼주면
			// 1000000000000000000000 에서 11111111111111111111이 된다. (개수가 맞나? 21개, 20개!)
			S = (1 << 21) - 1;
		}
		else if (a == "empty")
		{
			S = 0;
		}
	}


	return 0;
}