문제
비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.
문제 링크
https://www.acmicpc.net/problem/11723
풀이
비트마스킹을 이용하면 쉽게 해결할 수 있다.
들어오는 값이 1부터 20까지이고, 값이 중복해서 기록되는 경우가 없기 때문이다.
add 연산의 설명에 `S에 x가 이미 있는 경우에는 연산을 무시한다.` 라는 조항이 있기 때문에 중복된 값이 기록되는 일은 없다.
"그럼 배열로 풀어도 되는거 아닌가?"
배열로 풀어도 문제 자체의 해답은 나오지만, 300만번에 해당하는 연산을 처리하기에는 배열은 적합하지 못하다.
비트 연산이 배열에 접근하고 값을 수정하는 것보다 월등히 빠르기 때문에 비트 연산을 사용해야 겨우 시간 초과를 면할 수 있다.
프로그램 동작
우선은 하나의 변수, S를 다음과 같은 형태로 생각해보자. ▼
그 다음에 우리는 이 문제를 크게 두 가지 행동으로 해결할 수 있다.
첫번째는 비트 쉬프트, 두번째는 비트 연산이다.
각 연산을 하나씩 확인해보자.
add 동작
x에 값이 들어오면, 들어온 만큼 비트를 밀어준다.
만약에 x가 4라면, 4만큼 밀어주면 된다.
그 다음, S와 OR 연산을 해준다. ▼
둘 다 0인 경우에만 0이 되고, 그 외에는 모두 1이기 때문에 우리가 넣으려는 자리에 값이 있든 없든 값을 기록할 수 있다.
remove 동작
x에 값이 들어오면, 똑같이 들어온 만큼 비트를 밀어준다.
하지만 이번엔 모든 비트를 반전해준다. ▼
그 다음, S와 AND연산을 해준다.
논리 곱이기에 나머지 자리는 모두 1과 곱을 하므로 값을 그대로 유지하지만, 들어온 자리는 0이기 때문에 비트가 제거된다.▼
check 동작
x에 값이 들어오면, 들어온 만큼 비트를 밀어준다.
그 다음, S와 AND 연산을 해준다.
만약에 해당 위치에 비트가 1이라면 값이 0이 되지 않을 것이고, 그게 아니라면 값이 0이 될 것이다. ▼
toggle 동작
x에 값이 들어오면, 들어온 만큼 비트를 밀어준다.
그 다음 XOR 연산을 해준다.
둘이 다를 때 1이 되기 때문에, 해당 자리가 0이라면 1로, 해당 자리가 1이라면 들어온 값이 똑같이 1이기에 0이 된다. ▼
all 동작
이번에는 1을 21만큼 비트 쉬프트해준다.
거기서 1을 빼면, 1부터 20번째까지 모든 비트가 1이 된다,
이 값과 S를 OR 연산을 해주면 모두 1이 된다. ▼
empty 동작
가장 간단하다.
값을 0으로 선언해버리면 된다. ▼
C++ 코드
#include <iostream>
#include <string>
using namespace std;
int M, B;
void input() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> M;
}
void solution() {
string cmd;
int x;
while (M--) {
cin >> cmd;
if (cmd == "add") {
cin >> x;
B |= (1 << x);
} else if (cmd == "remove") {
cin >> x;
B &= ~(1 << x);
} else if (cmd == "check") {
cin >> x;
if (B & (1 << x))
cout << 1 << '\n';
else
cout << 0 << '\n';
} else if (cmd == "toggle") {
cin >> x;
B ^= (1 << x);
} else if (cmd == "all") {
B = (1 << 21) - 1;
} else if (cmd == "empty") {
B = 0;
}
}
}
void solve() {
input();
solution();
}
int main() {
solve();
}