[C++][백준] - 집합 (11723번)

https://www.acmicpc.net/problem/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) 만큼 주어집니다.

 

check를 실행할때마다 결과를 출력하면 됩니다.

---

🔔 Kick Point :

그냥 함수를 이용하여 구해도 되지만 비트마스크를 사용하면 더욱 코드의 길이를 줄이기 때문에 비트마스크를 사용했습니다.

 

add :

bit |= ( 1 << num) 의 의미는 

bit = bit | ( 1 << num) 이며, 더할때마다 1의 왼쪽 쉬프트로 인해 bit에 더햐여집니다.

bit = 0000 0000 이라 할때 num 가 1인경우 0000 0000 | 0000 0010  = 0000 0010이 됩니다. 따라서 오른쪽부터 두번째 자리에 1이 되어 1이 마스킹 된 것을 알 수 있습니다.

 

remove:

bit &= ~(1 << num)

bit = bit & ~( 1<< num) 이며 bit에 (1<<num) 자리의 마스킹을 0으로 둘 수 있게 됩니다.

 

check:

bit & ( 1<< num) 이 하면 만약 그 자리에 1이 있으면, 1로 나오기 때문에 체크할 수 있습니다.

 

toggle:

bit ^= (1 <<num) 이며, ^ 기호는 XOR 기호기 때문에 대응하는 두 비트가 서로 다르면 1을 반환합니다.

1 ^ 1 = 0

0 ^ 0 = 0

1 ^ 0 = 1

0 ^ 1 = 1 이 됩니다.

따라서 만약 

 

bit 1111 1010 이고, num이 1인 경우에 toggle 을 할경우 1111 1000이 되어야 합니다.

 

(1111 1010) ^ (0000 0010) = (1111 1000) 이 됨을 알 수있습니다.

 

all:

 x가 20까지이기 때문에 

(1 << 21) -1 을 하면 (0010 0000 0000 0000 0000 0000)  - (0000 0000 0000 0000 0000 0001) 이 되어 

0001 1111 1111 1111 1111 1111 이 됩니다. 이때 마지막 자리 1은 계산하기 쉽게 비어둔것이라 생각하면 됩니다.

 

empty:

비어있게 하기 위해선 

bit = 0 을 하면 자연스레 0으로 되어서 비워집니다.

---

🔔 Code :

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

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int m;
	int bit = 0, num = 0;
	string input;

	cin >> m;
	while (m--) {
		
		input.clear();
		cin >> input;
		
		if(input == "add"){
			cin >> num;
			bit |= (1 << num);
		}
		else if(input == "remove"){
			cin >> num;
			bit &= ~(1 << num);
		}
		else if(input == "check"){
			cin >> num;
			if (bit & (1 << num)) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else if (input == "toggle") {
			cin >> num;
			bit ^= (1 << num);
		}
		else if(input == "all"){
			bit = (1 << 21) - 1;
		}
		else if(input == "empty"){
			bit = 0;
		}
	}

}

---