백준 11723번 (집합) c++
문제
문제풀이
1. 비트마스킹을 이용해야 한다.
비트마스킹이란?
컴퓨터는 모든 데이터를 이진수로 표현한다. 그래서 이진수 표현을 자료구조로 쓰는 기법을 비트마스킹이라고 한다.
비트마스킹을 이용하면, 더 적은 메모리, 더 적은 시간을 사용하여 효율적으로 구현할 수 있다.
ex) a = 9, b = 7
1. a & b (AND)
a = 1001
b = 0111
a & b = 0001 = 1
2. a | b (OR)
a = 1001
b = 0111
a | b = 1111 = 15
3. a ^ b (XOR)
같은 비트라면 0으로, 틀리다면 1로 바꾼다.
a = 1001
b = 0111
a ^ b = 1110 = 14
4. ~a (NOT)
a = 1001
~a = 0110 = 6
5. <<, >> (SHIFT)
a = 1001 = 9
a << 1 = 0001 0010 = 18
a << 2 = 0010 0100 = 36
a << 3 = 0100 1000 = 72
a >> 1 = 0100 = 4
a >> 2 = 0010 = 2
a >> 3 = 0001 = 1
이렇게 비트마스킹을 이용하면 쉽게 집합 문제를 풀 수 있다.
S = 0 이라고 가정을 하고,
1. add
S |= (1 << x) 를 쓰면, 집합에 어떤 숫자가 있는지 표현할 수 있다.
ex) add 4
0 |= (1 << 4)
0000 0000
0001 0000
= 0001 0000 = 16
이렇게 쉽게 표현할 수 있다.
2. remove
S &= ~(1 << x) 를 쓰면,
ex) remove 4
18 &= ~(1 << 4)
0001 0010
1110 1111
= 0000 0010 = 2
딱 지우고 싶은 숫자만 지워지는 것을 볼 수 있다.
3. check
S & (1 << x) 이렇게 조건으로 줄 수 있다.
ex) check 4
18 & (1 << 4)
0001 0010
0001 0000
= 1
ex) check 18
18 & (1 << 18)
0000 0000 0000 0001 0010
0100 0000 0000 0000 0000
= 0
각 자리마다 숫자를 가지고 있는지 판단하기 때문에 S에 저장된 값이 18이여서 밑에 숫자가 더 있어도 무시하고 생각해도 된다.
4. toggle
이미 input으로 들어온 숫자가 존재하면 0으로 아니라면, 1로 바꾸는 명령어다.
그래서 add와 remove, check를 조합하여 쓴다면 간편하게 쓸 수 있다.
먼저 check로 존재하는지 판단을 하고 존재한다면 remove, 존재하지 않다면 add를 쓴다.
if(S & (1 << x)){
S &= ~(1 << x);
}
else{
S |= (1 << x);
}
또는, XOR를 이용할 수 있다.
S ^= (1 << x)
ex) toggle 4
18 ^= (1 << 4)
0001 0010
0001 0000
= 0000 0010 = 2
결국 해당 input이 존재하다면 그 input 숫자만 비교를 하기 때문에 toggle을 이렇게 XOR로 이용할 수도 있다.
5. all
S = (1 << 21) - 1;
(1 << 21) = 0001 0000 0000 0000 0000 0000
(1 << 21) - 1 = 0000 1111 1111 1111 1111 1111
이렇게 변하기 때문에 all은 간편하게 표현할 수 있다.
6. empty
S = 0
전체코드 (toggle XOR를 안쓴 경우)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int M;
cin >> M;
int S = 0;
for(register int m = 0; m < M; m++){
string input = "";
int x;
cin >> input;
if(input == "add"){
cin >> x;
S |= (1 << x);
}
else if(input == "remove"){
cin >> x;
S &= ~(1 << x);
}
else if(input == "check"){
cin >> x;
if(S & (1 << x)){
cout << "1\n";
}
else{
cout << "0\n";
}
}
else if(input == "toggle"){
cin >> x;
if(S & (1 << x)){
S &= ~(1 << x);
}
else{
S |= (1 << x);
}
}
else if(input == "all"){
S = (1 << 21) - 1;
}
else{
S = 0;
}
}
return 0;
}
전체코드 (toggle XOR를 쓴 경우)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int M;
cin >> M;
int S = 0;
for(register int m = 0; m < M; m++){
string input = "";
int x;
cin >> input;
if(input == "add"){
cin >> x;
S |= (1 << x);
}
else if(input == "remove"){
cin >> x;
S &= ~(1 << x);
}
else if(input == "check"){
cin >> x;
if(S & (1 << x)){
cout << "1\n";
}
else{
cout << "0\n";
}
}
else if(input == "toggle"){
cin >> x;
S ^= (1 << x);
}
else if(input == "all"){
S = (1 << 21) - 1;
}
else{
S = 0;
}
}
return 0;
}