> [!date] published: 2022-01-27
[11723번: 집합](https://www.acmicpc.net/problem/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` 연산이 주어질때마다, 결과를 출력한다.
## 🌟 풀이
언뜻 보기에는 그냥 벡터를 이용해서 구현하면 될 것 같지만... 연산의 수가 최대 3,000,000번이기 때문에 시간초과 무조건 걸릴 것이라고 생각했다. 어떻게 풀어야 할 지 감이 안서는 중에 문제가 비트마스킹에 분류되어 있는 것을 확인했고 그래서 비트마스킹을 활용해서 문제를 풀었다.
내가 이 문제를 풀기 위해서 이해 한 대로 간단히 설명해보면 비트마스킹이란 비트를 이용해서 집합을 다루는 것이다. 집합의 i번째 요소가 존재한다면 i번째 비트를 1로 표시하고, 존재하지 않는다면 0으로 표시하는 방법으로 집합의 삽입, 삭제, 조회를 비트 연산으로 구현할 수 있다.
나는 비트 연산에 좀 약해서 일단 bool 타입의 배열을 이용해서 먼저 문제를 풀어 준 다음에, 비트연산을 이용해서 한번 더 문제를 풀어줬다.
### ✨ 배열 활용하기
집합의 i번째 요소가 존재한다면 배열의 i번째 요소를 true로, 존재하지 않는다면 false로 표시해주는 방법으로 배열의 정보를 표시했다.
위의 방법으로 문제의 연산들을 구현해 주면 문제 자체는 간단하게 풀 수 있었는데, 입력과 출력의 횟수가 많으므로
```c
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
```
위의 코드를 추가해 줘서 느린 cin, cout 속도를 보완해주었다.
### ✨ 비트마스킹 활용하기
처음 아무 연산도 하지 않았을 때의 집합의 상태는 아래와 같은 상태일 것이고
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
(10 이후 생략)
집합를 set 라 하면 `int set = 0` 이라 할 수 있다.
#### add x
위의 집합에 1을 넣으려면 1번째 인덱스를 1로 만들어 주어야 한다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
이 값과 set를 `OR` 연산 해 주면 set의 1번째 비트를 1로 만들어 줄 수 있는데 `OR` 연산을 해 줄 위 값은
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
이렇게 표현되는 **1을 왼쪽으로 1번 `shift`** 해서 만들 수 있다.
비슷하게 2를 추가해 주려면 set의 2번째 비트를 1로 만들어 줘야 하고 그러러면
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
이 값과 set를 `OR` 연산해줘야 하는데 이 값은 **1을 왼쪽으로 2번 `shift`** 해서 만들 수 있다.
이런 규칙에 따라서 `add x` 연산은 아래와 같이 구현할 수 있다.
```c
set = set | (1 << x);
```
#### remove x
1과 2가 들어있는 집합의 상태이다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
위 집합에서 1번째 비트를 0으로 바꾸어줘야 1을 집합에서 제거할 수 있고,
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
위와 같이 1번째 비트를 제외한 모든 비트가 1인 값과 `AND` 연산을 해 주면 1번째 비트만 0으로 바꿀 수 있다.
위 내용을 일반화 해 보면 x번째 비트를 제거하기 위해 집합에 `AND` 연산해줄 그 값은 **1을 왼쪽으로 x번 `shift`한 값을 `NOT` 연산으로 비트를 반전**시켜서 만들 수 있다. 이 내용을 코드로 표현하면 다음과 같다.
```c
set = set & ~(1 << x);
```
#### check x
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
1이 들어있는 집합에서 1이 들어있는지 확인해주려면 집합과 1번째 비트를 제외한 모든 값이 0인 값을 `AND` 연산한 값을 확인해주면 된다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
이 값과 set를 `AND` 연산해주면 2(0이 아닌 값)가 나올 것이고, 이는 해당 집합에 1이 들어있다는 것을 의미한다.
마찬가지로 이 집합에 2가 들어있는지 확인해주기 위해서는 아래의 값과 `AND` 연산해주면 된다.
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
`AND` 연산의 결과는 0이 될 것이고, 이는 해당 집합에 2가 들어있지 않다는 것을 의미한다.
위의 규칙을 바탕으로 check x를 구현하면 다음과 같다.
```c
// 0이 아닌 경우
if (set & (1 << x))
cout << 1 << '\n';
// 0인 경우
else
cout << 0 << '\n';
```
#### toggle x
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
1과 2가 들어있는 집합에서 toggle 1을 하면 아래와 같은 상태가 될 것이고
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
다시 toggle 3을 하면 아래와 같이 될 것이다.
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
x번째 비트가 1인 경우에는 0으로 바꾸어주고, 0인 경우에는 1로 바꾸어주기 위해서는 x번째 비트를 제외한 비트가 0인 값과 `XOR` 연산을 해 주면 될 것이다. 집합의 x번째 비트가 1이라면 `1 XOR 1 = 0`이 되고, 0이라면 `0 XOR 1 = 1`이 되는 원리이다. 이 내용을 코드로 표현하면 다음과 같다.
```c
set = set ^ (1 << x);
```
#### all, empty
all은 모든 비트를 1로 만들어 줘야 하므로 0을 NOT 연산으로 반전시켜 주면 된다.
empty는 처음 set을 초기화 해 줬던 대로 값을 0으로 설정해 주면 된다.
```c
// all
set = ~0;
// empty
set = 0;
```
---
비트 연산, 비트 마스크에 대해서 참고한 글
[C 언어 코딩 도장: 23.1 비트 AND, OR, XOR 연산자 사용하기](https://dojang.io/mod/page/view.php?id=173)
[비트마스크(bit mask) : 네이버 블로그](https://m.blog.naver.com/jh20s/221150706030)
## 🌟 코드
### ✨ 배열
```c
/*
2022-1-27
11723_집합
https://www.acmicpc.net/problem/11723
*/
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
bool info[21];
int n, x;
string op;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(info, 0, sizeof(info));
cin >> n;
for(int t = 0; t < n; t++){
cin >> op;
if (op == "add"){
cin >> x;
info[x] = true;
}
else if (op == "remove"){
cin >> x;
info[x] = false;
}
else if (op == "check"){
cin >> x;
cout << info[x] << '\n';
}
else if (op == "toggle"){
cin >> x;
if (info[x])
info[x] = false;
else
info[x] = true;
}
else if (op == "all"){
for(int i = 1; i <= 20; i++)
info[i] = true;
}
else { // op == "empty"
for(int i = 1; i <= 20; i++)
info[i] = false;
}
}
return (0);
}
```
### ✨ 비트마스크
```c
/*
2022-1-27
11723_집합
https://www.acmicpc.net/problem/11723
*/
#include <iostream>
#include <string>
using namespace std;
int n, x;
int set = 0;
string op;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int t = 0; t < n; t++){
cin >> op;
if (op == "add"){
cin >> x;
set = set | (1 << x);
}
else if (op == "remove"){
cin >> x;
set = set & ~(1 << x);
}
else if (op == "check"){
cin >> x;
if (set & (1 << x))
cout << 1 << '\n';
else
cout << 0 << '\n';
}
else if (op == "toggle"){
cin >> x;
set = set ^ (1 << x);
}
else if (op == "all"){
set = ~0;
}
else { // op == "empty"
set = 0;
}
}
return (0);
}
```