[백준] Class3-집합 C++ 11723번

문제

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1 복사

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1 복사

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

 

소스코드:

#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int M;
int S[21];	//1~20까지의 x의 개수 배열
int x;
string a;

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

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> a;
		if (a == "add")
		{
			cin >> x;
			if (S[x] != 0)
				continue;
			else
				S[x]++;
		}
		if (a == "remove")
		{
			cin >> x;
			if (S[x] == 0)
				continue;
			else
				S[x]--;
		}
		if (a == "check")
		{
			cin >> x;
			if (S[x] != 0)
				cout << 1 << '\n';
			else
				cout << 0 << '\n';
		}
		if (a == "toggle")
		{
			cin >> x;
			if (S[x] != 0)
				S[x]--;
			else
				S[x]++;
		}
		if (a == "all")
		{
			for (int j = 1; j <= 20; j++)
			{
				if (S[j] == 0)
					S[j]++;
			}
		}
		if (a == "empty")
		{
			for (int j = 1; j <= 20; j++)
			{
				if (S[j] != 0)
					S[j]--;
			}
		}
	}

}

 

다른 소스코드:

#include <iostream>
using namespace std;

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

	int M;
	cin >> M;
	int s = 0;	//00000000 00000000 00000000 00000000
	
	while (M--)
	{
		string word;
		cin >> word;

		if (word == "add")
		{
			int x;
			cin >> x;
			s |= (1 << (x - 1));
		}
		else if (word == "remove")
		{
			int x;
			cin >> x;
			s &= ~(1 << (x - 1));
		}
		else if (word == "check")
		{
			int x;
			cin >> x;
			if (s & (1 << (x - 1)))
				cout << 1 << '\n';
			else
				cout << 0 << '\n';
		}
		else if (word == "toggle")
		{
			int x;
			cin >> x;
			s ^= (1 << (x - 1));
		}
		else if (word == "all")
		{
			s |= (1 << 20) - 1;
		}
		else if (word == "empty")
		{
			s = 0;
		}
	}
}

접근방법: 하나의 정수를 1~20까지의 x의 개수를 체크하는 배열로 사용해서 비트 마스킹(비트 연산)을 이용해 문제를 풀었다.