[백준] 11723번. 집합

leeeha·2022년 7월 13일

백준

목록 보기

47/186

문제

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

비어있는 공집합 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://blockdmask.tistory.com/79

C++에서 제공해주는 set 컨테이너를 사용해보았다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);

	int m;
	cin >> m;

	set<int> s; // 집합 (원소가 삽입되면 자동으로 정렬됨)
	
	while(m--){
		string str; 
		cin >> str; // 공백을 제외하고 입력 받기 

		int val;
		if(str == "add"){
			cin >> val;

			auto it = s.find(val); 
			if(it == s.end()){
				s.insert(val);
			} // 이미 있는 원소면 무시하기 
		}else if(str == "remove"){
			cin >> val;

			auto it = s.find(val);
			if(it != s.end()){
				s.erase(it); 
			} // 없는 원소면 무시하기 
		}else if(str == "check"){
			cin >> val;
			
			auto it = s.find(val);
			if(it != s.end()){
				cout << "1\n";
			}else{
				cout << "0\n"; 
			}
		}else if(str == "toggle"){
			cin >> val;
			
			auto it = s.find(val); 
			if(it != s.end()){ 
				s.erase(it); // 있으면 제거 
			}else{ 
				s.insert(val); // 없으면 추가 
			}
		}else if(str == "all"){
			s.clear();
			for(int i = 1; i <= 20; i++){
				s.insert(i);
			}
		}else{ // empty 
			s.clear();
		}
	}
	
	return 0;
}

답안

https://nanyoungkim.tistory.com/47

배열에 원소의 유무를 저장

#include <iostream>
#include <string> 
using namespace std;

// 1~20까지의 숫자가 집합에 포함되어 있는지 표시 
int arr[21]; // 0으로 초기화 

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);

	int m;
	cin >> m;

	string str;
	int x;
	while(m--){
		cin >> str;

		if(str == "add"){
			cin >> x;
			if(arr[x] == 0){
				arr[x] = 1; 
			}
		}else if(str == "remove"){
			cin >> x;
			if(arr[x] == 1){ 
				arr[x] = 0; 
			}
		}else if(str == "check"){
			cin >> x;
			if(arr[x] == 0){ 
				cout << "0\n"; 
			}else{ 
				cout << "1\n"; 
			}
		}else if(str == "toggle"){
			cin >> x;
			if(arr[x] == 0){ 
				arr[x] = 1;
			}else{ 
				arr[x] = 0; 
			}
		}else if(str == "all"){
			for(int i = 1; i <= 20; i++){
				arr[i] = 1;
			}
		}else if(str == "empty"){
			for(int i = 1; i <= 20; i++){
				arr[i] = 0; 
			}
		}
	}
	
	return 0;
}

비트 마스크 (bitmask)

2진수에서 left shift를 한번 하면 자릿수가 한칸 올라가므로, 곱하기 2를 한 것과 같다.
반대로 right shift 한번은 자릿수가 한칸 내려가는 것이므로, 나누기 2를 한 것과 같다.

a << b : a를 b칸만큼 왼쪽으로 이동 (곱하기)
a << 1 : a에 2를 곱한다.
a << 2 : a에 4를 곱한다.
a << 3 : a에 8을 곱한다.

a >> b : a를 b칸만큼 오른쪽으로 이동 (나누기)
a >> 1 : a에서 2를 나눈다.
a >> 2 : a에서 4를 나눈다.
a >> 3 : a에서 8을 나눈다.

이처럼 2진수의 비트로 연산을 하면, 수행시간이 빨라지고 메모리 사용량도 줄어든다. (10진수 8을 저장하려면 int형으로 32비트가 필요한데, 2진수로 8을 저장할 때는 1000 이렇게 4비트만 필요하니까 메모리 절약 가능)

그렇다면, 비트마스크는 뭘까? 비트로 가린다? 그렇다! 비트 연산자를 이용해서 원하는 값을 세팅하거나 제거할 수 있다. 비트 연산자에는 & (bitwise AND), | (bitwise OR), ^ (bitwise XOR), ~ (bitwise NOT) 등이 있다.

비트 연산자	정의	효과
& (AND)	둘 다 1이어야 1	bit masking (제거)
\| (OR)	둘 중에 하나만 1이어도 1	bit setting (추가)
~ (NOT)	비트 전환	bit inverting (1의 보수)

add 1, add 2, add 3이 입력으로 들어왔을 때 위의 그림처럼 left shift 연산자를 이용하여 ~~그 숫자 자체를 저장하는 것이 아니라~~ 마치 그 숫자가 2진수 비트의 자릿수인 것처럼 표시할 것이다!

이 문제에서 x는 1부터 20까지이므로 32비트면 충분하다. 20을 추가하고 싶을 때는 20번째 자릿수의 비트를 1로 표시하면 되기 때문이다.

s: 32비트
add: 입력값과 s를 or 연산
remove: 입력값을 not으로 뒤집고, 그 수를 s와 and 연산
check: s에 입력값이 있으면, s와 and 연산을 했을 때 결과가 1이 나옴.

s에 x가 있는지 확인하려면?
s : 0000 0110
1 << x : 2진수에서 x번째 비트를 1로 표시
s & (1 << x) : s에 x가 있다면, x번째 비트가 1로 살아있음. (위의 예시에서는 x가 1과 2일 때, and 연산의 결과가 1로 나옴.)
all: 1번째부터 20번째 비트까지 모두 1로 채운다. (1 << 21) - 1

1 << 21 : 0000 0000 0001 0000 0000 0000 0000 0000
1 : 0000 0000 0000 0000 0000 0000 0000 0001
substract: 0000 0000 0000 1111 1111 1111 1111 1110

#include <iostream>
#include <string> 
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);

	int m;
	cin >> m;

	int s = 0; // 32비트를 0으로 초기화 

	string str;
	int x;
	while(m--){
		cin >> str;

		if(str == "add"){
			cin >> x;
			s |= (1 << x); // bit setting 
		}else if(str == "remove"){
			cin >> x;
			s &= ~(1 << x); // bit masking 
		}else if(str == "check"){
			cin >> x;
			if(s & (1 << x)){ // exist 
				cout << "1\n";
			}else {
				cout << "0\n";
			}
		}else if(str == "toggle"){
			cin >> x;
			if(s & (1 << x)){ // exist 
				s &= ~(1 << x); // remove 
			}else {
				s |= (1 << x); // add
			}
		}else if(str == "all"){
			s = (1 << 21) - 1; // 1부터 20번째 비트 모두 1로 표시 
		}else if(str == "empty"){
			s = 0;
		}
	}
	
	return 0;
}