BOJ 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부터 20까지만 나오므로 집합 전체를 비트마스크 하나로 표현할 수 있다. add x는 x번째 비트를 켜고, remove x는 끄며, check x는 해당 비트가 켜져 있는지 검사하면 된다.

all은 전부 켜진 값으로, empty는 0으로 바꾸면 끝이다. 현재 코드는 각 명령을 비트 연산으로 바로 처리하기 때문에 배열이나 해시셋을 쓰는 것보다 훨씬 가볍게 구현된다.

코드#

#include <iostream>
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int M;
	cin >> M;
 
	string s;
	int n, bit = 0;
 
	while (M--) {
		cin >> s;
 
		if (s == "add") {
			cin >> n;
			bit |= (1 << n);
		}
		else if (s == "remove") {
			cin >> n;
			bit &= ~(1 << n);
		}
		else if (s == "check") {
			cin >> n;
			if (bit & (1 << n))
				cout << "1" << '\n';
			else
				cout << "0" << '\n';
 
		}
		else if (s == "toggle") {
			cin >> n;
			if (bit & (1 << n))
				bit &= ~(1 << n);
			else
				bit |= (1 << n);
		}
		else if (s == "all") {
			bit |= ~0;
 
		}
		else if (s == "empty") {
			bit &= 0;
		}
	}
 
 
	return 0;
}

복잡도#

• 시간 복잡도: $M$개의 집합 명령을 비트마스크로 상수 시간에 처리하므로 $O(M)$이다.
• 공간 복잡도: 정수 비트마스크 하나만 사용하므로 $O(1)$이다.

마무리#

원소가 1부터 20까지만 나오므로 집합 전체를 비트마스크 하나로 표현할 수 있다.