11723 집합 - 비트마스크

벡터로도 구현할 수 있긴 하지만,
메모리 제한이 4MB이므로 비트마스크를 통한 풀이가 필요하다.

이런 풀이 접근법이 있다는 것을 들어는 보았지만
직접 풀어본 적은 없어서
한번 적어보려고 한다.

그리 어려운 풀이는 아니다.

원소의 범위가 1~9이고
집합 S = {1,2,3,4,9}가 있다고 할 때,
S에 존재하는 원소들을 어떤 방법으로 효율적으로 나타낼 수 있을까?

100001111

오른쪽에서부터 첫 번째라고 했을 때
해당 자리가 1로 되어있으면 원소가 존재한다고 여긴다.
오른쪽에서부터 첫 번째 ~ 네번째까지 자릿수가 1이므로
원소 1~4가 존재하고,
다섯 번째 ~ 여덟번째는 자릿수가 0이므로
원소 5~8은 존재하지 않는 것이다.

코드

#include <iostream>

using namespace std;

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

	int m, x;
	cin >> m;
	int set = 0;

	for (int i = 0; i < m; i++)
	{
		string s;
		cin >> s;

		

		if (s == "add")
		{
			cin >> x;
			set = set | (1 << (x - 1));
		}

		else if (s == "remove")
		{
			cin >> x;
			set = set & ~(1 << (x - 1));
		}

		else if (s == "check")
		{
			cin >> x;

			
			cout << (((set & (1 << (x - 1))) == 0) ? "0" : "1");
			cout << '\n';
		}

		else if (s == "toggle")
		{
			cin >> x;

			set = set ^ (1 << (x - 1));
		}

		else if (s == "all")
			set = (1 << 19) + ~(1 << 19);

		else if (s == "empty")
			set = 0;
		
	}

}

여기서 s == "all"일 때

set = (1 << 21) - 1;

과 같이 간단하게 나타낼 수도 있다.