BOJ 11723 - 집합

집합 - 🥈 Silver 5

• 문제 링크
  https://www.acmicpc.net/problem/11723

입력값의 범위가 1 <= x <= 20 으로 짧게 주어졌기 때문에 특정 STL을 이용하여 해당 연산들을 구현하는 방식보다는 BitMask 방식을 활용하는 것이 더 좋아보였다.

처음 해당 문제를 풀이한 방식은 bool vector 를 이용하여 유사한 방식으로 아래와 같이 처리하였다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int M, X;
string input;
vector<bool> S(20, false);
vector<bool> falseS(20, false);
vector<bool> trueS(20, true);

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

	cin >> M;
	while (M--) {
		cin >> input;
		if (input == "add") {
			cin >> X;
			S[X - 1] = true;
		}
		else if (input == "remove") {
			cin >> X;
			S[X - 1] = false;
		}
		else if (input == "check") {
			cin >> X;
			if (S[X - 1]) cout << 1 << "\n";
			else cout << 0 << "\n";
		}
		else if (input == "toggle") {
			cin >> X;
			S[X - 1] = !S[X - 1];
		}
		else if (input == "all") S = trueS;
		else if (input == "empty") S = falseS;
		else cout << "invalid command input\n";
	}

	return 0;
}

하지만 이보다 더 효율적이게 O(1) time 에 작동하는 비트 연산을 활용한 BitMask 방식을 활용하여 아래와 같이 다시 풀이하였다.

풀이 코드

#include <iostream>
#include <string>
using namespace std;

int M, X, bit;
string input;

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

	cin >> M;
	while (M--) {
		cin >> input;
		if (input == "add") {
			cin >> X;
			bit |= (1 << X);
		}
		else if (input == "remove") {
			cin >> X;
			bit &= ~(1 << X);
		}
		else if (input == "check") {
			cin >> X;
			if (bit & (1 << X)) cout << 1 << "\n";
			else cout << 0 << "\n";
		}
		else if (input == "toggle") {
			cin >> X;
			bit ^= (1 << X);
		}
		else if (input == "all") bit = (1 << 21) - 1;
		else if (input == "empty") bit = 0;
		else cout << "invalid command input\n";
	}

	return 0;
}

결과