[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을 출력한다.
• 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

---

문제 풀이

짧은 수행시간과 메모리 사용량을 충족하기 위해 비트마스크를 사용했다.

/* 비트마스크를 이용한 집합 연산 */
/* 2019-08-16 집합 */
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
	int tcase;
	int a = 0;

	scanf("%d", &tcase);
	for (int i = 0; i < tcase; i++) {
		char tmp[10];
		int x;
		scanf("%s", tmp);
		if (strcmp(tmp, "add") == 0) {
			scanf("%d", &x);
			a |= (1 << x);
		}
		else if (strcmp(tmp, "remove") == 0) {
			scanf("%d", &x);
			a &= ~(1 << x);
		}
		else if (strcmp(tmp, "check") == 0) {
			scanf("%d", &x);
			if (a & (1 << x)) printf("1\n");
			else printf("0\n");
		}
		else if (strcmp(tmp, "toggle") == 0) {
			scanf("%d", &x);
			a ^= (1 << x);
		}
		else if (strcmp(tmp, "all") == 0) {
			a = (1 << 21) - 1;
		}
		else if (strcmp(tmp, "empty") == 0) {
			a = 0;
		}
	}
}

비트마스크란 이진수 표현체계를 이용해 하나의 변수를 배열처럼 사용하는 것이다. 예를들어 1011 1100 인 경우 이 숫자가 표현하는 집합은 {2,3,4,5,7} 이고 이러한 숫자가 켜져 있다고 이야기 한다. 즉 x의 범위가 1부터 20이기 때문에 간단하게 21bit를 이용해 하나의 자리가 하나의 원소를 뜻하게 사용하면 된다.

가장 문제였던 부분은 시간초과였다. cin, cout을 사용하니까 시간초과가 나서 단순히 scanf, printf로 바꿔주니 문제를 해결할 수 있었다.

사실 공집합 S를 표현하기 위해 unsigned int를 처음에 사용했지만 int가 4byte이고 우리는 21bit만을 사용하기 때문에 최상위 비트의 부호문제는 생각하지 않아도 됐다.

비트마스크에 대한 자세한 내용은 종만북에 나와있으니 공부하면 좋을 것 같다.