[백준] 11723번: 집합 [C++]

 

알고리즘 분류: 구현, 비트마스킹

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

11723번: 집합

 

 

【 풀이 】

 

비트마스크 알고리즘을 활용하여 푸는 문제이다.

비트마스크란 이진수를 사용하는 컴퓨터 연산 방식을 이용해, 정수의 이진수 표현을 구현하는 데 사용되는 알고리즘이다.

비트연산을 이용하면, 원하는 숫자에 해당하는 인덱스의 비트를 0 또는 1로 표현하면서 집합을 구현해낼 수 있다.

• &    비트단위로 AND 연산
•  |     비트단위로 OR 연산
• ^     비트단위로 XOR 연산
• ~     단항연산자. 피연산자의 모든 비트를 반전
• <<   피연산자의 비트 열을 왼쪽으로 이동
• >>   피연산자의 비트 열을 오른쪽으로 이동

 

 

【 코드 】

 

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

int main(void)
{
	int S = 0;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		cout.tie(NULL);

		string s;
		cin >> s;
        
		if (s == "add")	{
			int num;
			cin >> num;
			S |= (1 << num);
		}
        
		else if (s == "remove"){
			int num;
			cin >> num;
			S &= ~(1 << num);}
            
		else if (s == "check"){
			int num;
			cin >> num;
			if (S & (1 << num))
				cout << 1<<'\n';
			else
				cout << 0<<'\n';
		}
        
		else if (s == "toggle"){
			int num;
			cin >> num;
			S ^= (1 << num);
		}
        
		else if (s == "all")
			S = (1 << 21) - 1;
            
		else if (s == "empty")
			S = 0;
	}
	return 0;
}