[BOJ/C++] 11723(집합)

Link

https://www.acmicpc.net/problem/11723

풀이 과정

*일반적인 문제에서는 메모리를 기본으로 512MB, 256MB를 주는 편인데, 이렇게 4MB, 1MB 등의 형태로 나온다면 비트단위 연산이 필요할 것으로 판단하면 좋습니다.(int나 long, char 등의 자료형에서 0,1만을 사용하여 비트마스킹)

1. 메모리 제한 -> 비트마스킹, 배열 등 자료구조 없는 단순 구현
2. 1<=x<=20 -> 2^20 비트마스킹

정답 코드

#include<iostream>
using namespace std;

int n, answer = 0, x = 1;

void input() {
	cin >> n;
}

void add(int num) {
	answer |= (x << --num);
}

void remove(int num) {
	if(answer & (x << (num - 1)))
		answer ^= (x << --num);
}

int check(int num) {
	if (answer & (x << --num)) return 1;
	return 0;
}

void toggle(int num) {
	answer ^= (x << --num);
}

void all() {
	answer = 0b11111'11111'11111'11111;
}

void solution() {
	input();
	string cmd;
	int num;
	for (int i = 0; i < n; ++i) {
		cin >> cmd;
		if (!(cmd == "all" || cmd == "empty")) cin >> num;
		if (cmd == "add") add(num);
		else if (cmd == "remove") remove(num);
		else if (cmd == "check") cout << check(num) << '\n';
		else if (cmd == "toggle") toggle(num);
		else if (cmd == "all") all();
		else answer = 0;
	}
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}