[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 집합 (11723)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 집합 (11723)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 집합 (11723)

 

---

 

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 연산이 주어질때마다, 결과를 출력한다.

---

[ 코드 ]

 

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

// 비트마스크 계산 활용
// 보통 0부터 N-1까지 정수로 이루어진 집합을 나타낼 때 사용한다. (all을 사용할 땐 N으로 구ㅜ함)
// 정수로 집합을 나타낼 수 있음. {1, 3, 4, 5, 9} = 2^1 + 2^3 + 2^4 + 2^5 + 2^9 = 570

// 배열을 사용하는 것이 편리하지만, 비트마스크를 사용하는 이유는, 집합을 배열의 인덱스로 사용하 ㄹ수 있기 때문이다.
// 상태 다이나믹을 할 때 자주 사용하게 된다.

int ans = 0; // 정수 집합

void BM(string s) {
	int x;

	if (s == "add")
	{
		cin >> x;
		if ((ans & (1 << x)) == 0) // x값이 S내부에 존재하지 않을 때
		{
			// x 추가하기 방법
			ans = (ans | (1 << x)); // 1<<x은 1 * 2^x과 같은 의미 
			// or 연산자
		}
	}
	else if (s == "remove")
	{
		cin >> x;
		if ((ans & (1 << x)) != 0) // x값이 S내부에 존재할 때
		{
			// x 제거하기 방법
			ans = (ans & ~(1 << x));  // and 연산자
		}
	}
	else if (s == "check")
	{
		cin >> x;
		if ((ans & (1 << x)) == 0) // x값이 S내부에 존재하지 않을 때
		{
			cout << 0 << '\n';
		}
		else // x값이 S내부에 존재할 때
		{
			cout << 1 << '\n';
		}
	}
	else if (s == "toggle")
	{
		cin >> x;
		ans = (ans ^ (1 << x));
		// xor 연산자 (같지 않으면 1을 출력)

	}
	else if (s == "all")
	{
		ans = (1 << 21) - 1; // 연산자 우선순위를 막기 위해 1<<20에 ()표시해주기
	}
	else if (s == "empty")
	{
		ans = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int M; // 수행해야 하는 연산의 수
	cin >> M;

	while (M--)
	{	
		string s;

		s.clear();
		cin >> s;

		BM(s);
	}

	return 0;
}