백준 11723(집합) C++

집합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1.5 초

4 MB (하단 참고)

47135

14637

10296

29.654%

문제

비어있는 공집합 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<string>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string order;
	int Bit=0, val;
	int m;
	cin >> m;
	while (m--) 
	{
		cin >> order;
		if (order == "add")
		{
			cin >> val;
			Bit |= (1 << val-1); 
		}
		else if (order == "remove")
		{
			cin >> val;
			Bit &= ~(1 << val-1); 
		}
		else if (order == "check")
		{
			cin >> val;
			if (Bit & (1 << val - 1))
				cout << 1 << '\n';
			else
				cout << 0 << '\n';
		}
		else if (order == "toggle")
		{
			cin >> val;
			Bit ^= (1 << val-1); //1^1 = 0, 0^1 = 1
		}
		else if (order == "all")
		{
			Bit = (1 << 20) - 1; // ex) 100000-1 = 11111
		}
		else if (order == "empty")
		{
			Bit = 0;
		}
	}
	return 0;
}

 

<풀이>

비트마스크를 사용해 푸는 문제였다.

집합에 1을 추가하면 Bit는 1이 되고, 여기에 3을 추가하면 101, 5를 추가하면 10101이 된다.

• And 연산 (&): 대응하는 두 비트가 모두 1이면 1 반환
  1010 & 1111 = 1010
• OR 연산 ( | ): 대응하는 두 비트 중 하나라도 1이면 1 반환
  1010 & 1111 = 1111
• Shift 연산 («,») : 비트를 왼쪽 또는 오른쪽으로 한칸씩 이동
  0011 « 2 = 1100
  1010 » 1 = 0101
• XOR 연산 (^): 대응하는 두 비트가 다르면 1 같으면 0 반환
  1010 ^ 1100 = 0110
• Not 연산 (~) : 비트를 반전
  ~1111 = 0000