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

11723번: 집합

비트마스크를 이용해 집합을 표현해서 푸는 문제이다.

S {1, 4, 5} = 11001

이렇게 S에 들어가 있는 원소는 1로, 없으면 0으로

생각하면 된다.

 

연산의 핵심은

1 << x

이다.

SHIFT로 1의 위치를 적절하게 조절하여 비트연산을 하면 된다.

 

ex)

S {1, 5} = 10001에 4를 add하고 싶다면,

1을 왼쪽으로 3bit 만큼 옮겨준다.

1 << 3

그러면 1000이 되는데,

이 값을 S와 OR 연산 해주면

01000

10001

----------

11001

 

4도 추가된 S {1, 4, 5} = 11001을 얻을 수 있다.

 

코드 작성하는 건 쉬웠는데..

완성하고 보니 한 눈에 알아보기 어려워서

나중에 다시 볼 때 왜 이렇게 했는지 해석하기 쉽지 않을 거 같다ㅎㅎ

익숙해지면 나아지겠지?

#include <iostream>
#include <bitset>
using namespace std;
int M, S, x;
string order;
bitset <20> bit;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> order;
		if (!(order == "all" || order == "empty")) cin >> x; // all이나 empty는 x를 받을 필요 없음

		if (order == "add") S |= 1 << x - 1;
		else if (order == "remove") S &= ~(1 << x - 1);
		else if (order == "check") cout << ((S & (1 << x - 1)) ? 1 : 0) << "\n";
		else if (order == "toggle") S ^= 1 << x - 1;
		else if (order == "all") S = ~(0 << 19);
		else S = 0;
		bit = bitset<20>(S); // 디버깅 용
	}
	return 0;
}