[Silver V] 집합 - 11723

문제 링크

성능 요약

메모리: 2024 KB, 시간: 560 ms

분류

비트마스킹, 구현

제출 일자

2024년 8월 18일 17:24:05

문제 설명

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

제출 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

int BIT = 0;

void add();
void remove();
void check();
void toggle();
void all();
void empty();

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

	freopen("input.txt", "r", stdin);
	
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		string s;
		cin >> s;
		if (s == "add") add();
		else if (s == "remove") remove();
		else if (s == "check") check();
		else if (s == "toggle") toggle();
		else if (s == "all") all();
		else if (s == "empty") empty();
	}
	return 0;
}

void add() {
	int i;
	cin >> i;
    // 0100
    // 0010
    // ---- or
    // 0110
    // 만약 같은 자리라면 1|1=1라서 문제없다. 
	BIT |= (1 << i);
}
void remove() {
	int i;
	cin >> i;
    // 0010 을 지우고 싶다면,,
    // ~(0010) = 1101

    // 0010
    // 1101
    // ---- and
    // 0000
    // and 연산에서 1이랑 연산되는 숫자는 자신의 값을 유지하게 된다. 0을 만나게 되면 어떤 숫자든 결과는 0을 도출한다.(remove)
	BIT &= ~(1 << i);
}
void check() {
	int i;
	cin >> i;
    // 해당 자리의 비트와 and연산하여 결과값으로 분기
	if (BIT & (1 << i)) cout << 1 << "\n";
	else cout << 0 << "\n";
}
void toggle() {
	int i;
	cin >> i;
    // xor 연산에서 1과 만나는 값은 모두 반전의 값이 결과로 나타난다.
    // 1 ^ 1 = 0    1 -> 0
    // 1 ^ 0 = 1    0 -> 1
	BIT ^= (1 << i);
}
void all() {
    // 1 ~ 20 까지의 수.. 2^21 - 1 을 하면 2^20 까지 1이 전부 채워진 수이다. 하지만 2^0 자리는 쓰지 않기 때문에 1을 제외외
	BIT = (1 << 21) - 1;
}
void empty() {
	BIT = 0;
}

실패한 처음 시도했던 방법

처음에는 set 자료형을 사용해 아래처럼 구현하였으나, 알아보니 set은 대규모의 데이터를 다루기에는 성능 면에서 좋지 않다고 한다. 시간 초과로 계속해서 에러가 떠서 결국 다른 방법을 참고하여 작성하였다.

void add() {
	int i;
	cin >> i;
	sets.insert(i);
}
void remove() {
	int i;
	cin >> i;
	sets.erase(i);
}
void check() {
	int i;
	cin >> i;
	cout << sets.count(i) << "\n";
}
void toggle() {
	int i;
	cin >> i;
	if (sets.count(i)) sets.erase(i);
	else sets.insert(i);
}
void all() {
	//for문을 이용한 방법
	set<int> mySet;
	for (int i = 1; i <= 20; i++)
	{
		mySet.insert(i);
	}
	sets = mySet;
}
void empty() {
	sets = {};
}

비트마스킹 기법을 사용해 해결

알고리즘이라기 보다는 일종의 기법이라고 할 수 있겠다.

예를 들어, 아래의 8비트가 있다면, 1 ~ 7까지의 숫자를 비트마스킹 기법으로 저장할 수 있다.

0	0	0	0	0	0	0	0

ADD 1을 한다면 2^1 자리를 1로

0	0	0	0	0	0	1	0

ADD 2을 한다면 2^2 자리를 1로

0	0	0	0	0	1	1	0

이런식으로 바꿔주면 문제의 5가지 기능을 구현하는 것이 가능하다.

문제에서는 x의 범위가 1~20이기 때문에 4바이트인 int형 자료형을 사용하면 32비트로 커버가 되어서 int형을 사용하였다.