[Baekjoon/C++] 11723번 - 집합

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

---

예제 입력	예제 출력
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 0 1 0 1 0 1 0 1 1 0 0 0 1 0

---

풀이

#include <iostream>
using namespace std;

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

	int M; // 연산의 수
	cin >> M;

	int x, bit = 0;

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

		switch (s[1])
		{
		case 'd': // S에 x를 추가한다.
			cin >> x;

			bit |= (1 << x);
			break;

		case 'e': // S에서 x를 제거한다.
			cin >> x;

			bit &= ~(1 << x);
			break;

		case 'h': // S에 x가 있으면 1을, 없으면 0을 출력한다.
			cin >> x;

			if (bit & (1 << x))
				printf("1\n");
			else
				printf("0\n");
			break;

		case 'o': // S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.
			cin >> x;

			bit ^= (1 << x);
			break;

		case 'l': // S를{ 1, 2, ..., 20 } 으로 바꾼다.
			bit = (1 << 21) - 1;
			break;

		case 'm': // S를 공집합으로 바꾼다.
			bit = 0;
			break;
		}
	}

	return 0;
}

 

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

cin를 빠르게 해서 입력받는 시간을 줄이기 위해 위의 코드를 추가했다.

 

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

		switch (s[1])
		{
		case 'd': // S에 x를 추가한다.
			cin >> x;

			bit |= (1 << x);
			break;

		case 'e': // S에서 x를 제거한다.
			cin >> x;

			bit &= ~(1 << x);
			break;

		case 'h': // S에 x가 있으면 1을, 없으면 0을 출력한다.
			cin >> x;

			if (bit & (1 << x))
				printf("1\n");
			else
				printf("0\n");
			break;

		case 'o': // S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다.
			cin >> x;

			bit ^= (1 << x);
			break;

		case 'l': // S를{ 1, 2, ..., 20 } 으로 바꾼다.
			bit = (1 << 21) - 1;
			break;

		case 'm': // S를 공집합으로 바꾼다.
			bit = 0;
			break;
		}
	}

수행해야하는 연산의 이름을 보면 s[1]의 스펠링이 서로 모두 다르다는 것을 알 수 있다. switch문에서는 문자열을 사용할 수 없으므로 s[1]을 대신 사용했다.

 

 

 

 

비트마스크에 대해서는 아래 블로그로 공부했다.

https://rebro.kr/63

비트마스크 (BitMask) 알고리즘