백준 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를 공집합으로 바꾼다.

문제 분류

• 구현
• 비트마스킹

문제 풀이

이 문제를 보고 트리 혹은 배열로 풀 수 있다고 생각했었지만, all과 empty의 연산을 보고 안 되겠다 싶었다. 트리 혹은 배열로 구현하여 all과 empty를 구현하려면 for문을 0에서부터 20번 돌아야되는데, m의 최댓값이 3,000,000이므로 너무 오래 걸린다. 즉, 비트마스킹을 이용해야 한다.

1번부터 20번까지의 수를 각각 비트로 대응시킨다. 맨 오른쪽 1번 비트가 1이면 s에 1이 있다는 거고, 0이면 없다는 뜻이 된다. 즉 all의 연산을 할 경우에는 s에 1^20-1(1,048,575)을 대입시키기만 하면 되고, empty의 경우 s에 0을 대입하면 된다.

add의 경우 해당 비트값만 1로 주고, 비트 OR연산을 수행하면 된다. remove는 해당 비트값을 1로 준 뒤, NOT연산으로 뒤집고, (100 -> 011로 만드는 작업) 해당 결과값과 s를 AND연산 하면 된다.

check는 그냥 해당 비트만 1로 주고, 그 값과 s로 AND연산을 수행하면 된다. 해당 비트(k번째)에 값이 있을 경우, 1 << k의 값이 되고, 값이 없으면 0이 되는 것을 이용하여 판별한다. toggle은 해당 비트를 1로 주는 연산을 한 뒤, s와의 XOR연산으로 해결한다.

각 k번째의 비트가 k의 포함 유무라고 생각하면 된다.

단순히 std::cin을 사용하면 시간초과가 나서 char[]을 이용하였다.

풀이 코드

#include <stdio.h>
#include <cstring>

int main()
{
	int s = 0, m, par;
	char in[10];
	scanf("%d", &m);
	while (m--) {
		scanf("%s", in);
		if (!strcmp(in, "add")) {
			scanf("%d", &par);
			s |= 1 << (par - 1);
		}
		else if (!strcmp(in, "remove")) {
			scanf("%d", &par);
			s &= ~(1 << (par - 1));
		}
		else if (!strcmp(in, "check")) {
			scanf("%d", &par);
			printf("%d\n", (s & (1 << (par - 1))) != 0);
		}
		else if (!strcmp(in, "toggle")) {
			scanf("%d", &par);
			s ^= 1 << (par - 1);
		}
		else if (!strcmp(in, "all")) s = 1048575;
		else s = 0;
	}
	return 0;
}