11723. 집합

2022-01-27
baekjoon
백준 11723번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

11723번: 집합

풀이

아이디어

언뜻 보기에는 그냥 벡터를 이용해서 구현하면 될 것 같지만… 연산의 수가 최대 3,000,000번이기 때문에 시간초과 무조건 걸릴 것이라고 생각했다. 어떻게 풀어야 할 지 감이 안서는 중에 문제가 비트마스킹에 분류되어 있는 것을 확인했고 그래서 비트마스킹을 활용해서 문제를 풀었다.

내가 이 문제를 풀기 위해서 이해 한 대로 간단히 설명해보면 비트마스킹이란 비트를 이용해서 집합을 다루는 것이다. 집합의 i번째 요소가 존재한다면 i번째 비트를 1로 표시하고, 존재하지 않는다면 0으로 표시하는 방법으로 집합의 삽입, 삭제, 조회를 비트 연산으로 구현할 수 있다.

나는 비트 연산에 좀 약해서 일단 bool 타입의 배열을 이용해서 먼저 문제를 풀어 준 다음에, 비트연산을 이용해서 한번 더 문제를 풀어줬다.

배열 활용하기

집합의 i번째 요소가 존재한다면 배열의 i번째 요소를 true로, 존재하지 않는다면 false로 표시해주는 방법으로 배열의 정보를 표시했다.

위의 방법으로 문제의 연산들을 구현해 주면 문제 자체는 간단하게 풀 수 있었는데, 입력과 출력의 횟수가 많으므로

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 연산은 아래와 같이 구현할 수 있다.

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 연산으로 비트를 반전시켜서 만들 수 있다. 이 내용을 코드로 표현하면 다음과 같다.

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를 구현하면 다음과 같다.

// 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이 되는 원리이다. 이 내용을 코드로 표현하면 다음과 같다.

set = set ^ (1 << x);

all, empty

all은 모든 비트를 1로 만들어 줘야 하므로 0을 NOT 연산으로 반전시켜 주면 된다. empty는 처음 set을 초기화 해 줬던 대로 값을 0으로 설정해 주면 된다.

// all
set = ~0;
// empty
set = 0;

비트 연산, 비트 마스크에 대해서 참고한 글

코드

✨ 배열

/*
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);
}

✨ 비트마스크

/*
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);
}