백준 11723 집합 (c++) : 피너클

https://www.acmicpc.net/problem/11723

비트 연산자를 사용하는 문제다.

 

문제를 보면 S에 1 ~ 20을 넣어야 한다. 중요한게 1~20 인 것이다. 0~ 19 가 아닌 1 ~ 20 이다.

s = (1 << 21);

그렇기에 1에서 21만틈 옆으로 shift해주었다.

 

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.

shift 연산자 (<<) 와 OR 연산자 ( | ) 를 사용할 것이다.

 

<<는 x만큼 왼쪽으로 shift하는 연산자인데

s가 0000 0001 이고 4만큼 shift해야 하면 4칸 옮긴 0001 0000이 되는 것이다.

0110 0011 에서 4만큼 shift를 하면 1000 1100이 된다.

 

| 는 두 정수중 비트가 하나라도 1 이면 1로 남겨둔다. 아래처럼 말이다.

1110 0100

0000 0010 |

--------------

1110 0110 

s = s | (1 << x);

위의 코드를 봐보자. 1은 비트가 0000 0001이다. x가 4라고 가정하고

(1<<4) 는 0001 0000이 된다. 그리고 s가 0000 0000이라고 가정하고

s | (1<<4) == (0000 0000) | (0001 0000) == 0001 0000이 된다.

s가 0001 0000이라도 결과는 같으니 add가 완성된 것이다.

 

• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.

이번에는 AND연산자 (&)와 NOT연산자 (~)가 추가된다.

&연산자는 두 정수중 둘다 비트가 켜져있는것만 남겨둔다. 아래처럼 말이다.

1010 1100

1011 0110 &

--------------

1010 0100 

 

~연산자는 모든 비트를 뒤집는다. 아래처럼 말이다.

0110 0010

--------------

1001 1101 

s = s & ~(1 << x);

x를 4라 가정하고 (0001 0000)

~연산자를 사용하면 모든 비트가 뒤집혀 1110 1111이 된다. s가 0000 0000이라 가정하고 

s & ~(1 << 4) == (0000 0000) & (1110 1111) == 0000 0000 이 된다. s가 0001 0000이라면 

(0001 0000) & (1110 1111) == (0000 0000) 이 되고 s가 1101 0110 이라면

(1101 0110) & (1110 1111) == (1100 0110) 으로 우리가 원하는 대로 작동된다.

 

• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)

AND와 SHIFT를 사용한다.

if (s & (1 << x))

위에서 s & (1 << x)는 0 혹은 1<<x를 반환한다. 그러니

if(s & (1 << x) == 1) 아니면 if(s & (1 << x) == true) 이런 식으로 쓰면 작동이 잘 안될 것이다.

s안에 1<<x가 있으면 1<<x가 반환될거고 없으면 0이 반환될거니 잘 작동된다.

 

• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)

toggle 연산자 ( ^ ) 를 사용할 것이다.

^ 연산자는 XOR연산자로도 불리고 두 정수에서 하나는 1이고 하나는 0이면 1로 만들고 나머지는 전부 0이다.

1100 0111

0110 0101 ^

--------------

1010 0010 

s = s ^ (1 << x);

x를 4라 가정하고 (0001 0000) s는 (0000 0000)

s ^ (1 << 4) == (0000 0000) ^ (0001 0000) == (0001 0000)

s가 (0001 0000)이라면 

s ^ (1 << 4) == (0001 0000) ^ (0001 0000) == (0000 0000)

잘 작동된다.

• all: S를 {1, 2, ..., 20} 으로 바꾼다.

그냥 초기화 하면 된다.

s = (1 << 21) - 1;

1을 21만큼 shift하면 10 0000 0000 0000 0000 0000이 된다. 여기에서 1을 뺀다면

01 1111 1111 1111 1111 1111이 된다. 

01 1111 1111 1111 1111 1111에다가

00 0000 0000 0000 0000 0001을 더하면 10 0000 0000 0000 0000 0000이 되니 맞다.

 

• empty: S를 공집합으로 바꾼다.

위에서 1을 안빼면 된다.

s = (1 << 21);

 

#include <iostream>
#include <string>

using namespace std;

int m;
string str;
int x;
int s;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	s = (1 << 21);
	cin >> m;
	while (m-- > 0) {
		cin >> str;

		if (str == "add") {
			cin >> x;
			s = s | (1 << x);
		}
		else if (str == "remove") {
			cin >> x;
			s = s & ~(1 << x);
		}
		else if (str == "check") {
			cin >> x;
			if (s & (1 << x)) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else if (str == "toggle") {
			cin >> x;
			s = s ^ (1 << x);
		}
		else if (str == "all") {
			s = (1 << 21) - 1;
		}
		else if (str == "empty") {
			s = (1 << 21);
		}
	}
}

전체코드다.