8. 백준 C++[11723] 집합

[11723] 집합

---

 

난이도: Silver 5

시도횟수: 3

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를 공집합으로 바꾼다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;




int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	int M;
	cin >> M;
	int Set[20];
	for (int i = 0; i < 20; i++) {
		Set[i] = 0;
	}

	for (int j = 0; j < M; j++) {
		string cmd;
		int num;
		cin >> cmd;
		if (cmd != "all" && cmd != "empty") {
			cin >> num;
			num -= 1;
		}
		if (cmd == "all") {
			for (int i = 0; i < 20; i++) {
				Set[i] = 1;
			}
		}

		else if (cmd == "empty") {
			for (int i = 0; i < 20; i++) {
				Set[i] = 0;
			}
		}

		else if (cmd == "add") {
			Set[num] = 1;
		}
		else if (cmd == "remove") {
			Set[num] = 0;
		}
		else if (cmd == "check") {
			cout << Set[num] << '\n';
		}
		else if (cmd == "toggle") {
			Set[num] = (Set[num] + 1) % 2;
		}


	}

	
	return 0;
}

 

처음에는 c++의 STL인 set을 사용해서 구현하려 했다. 그런데 연산의 수가 3백만이라 stl을 사용하는 경우 무조건 시간초과가 날 수 밖에 없다. 그래서 비트마스킹이라는 알고리즘을 써야한다.

 

공집합을 00000000000000000000으로 두면 S.insert나 S.remove와 같은 method보다 훨씬 빠르게 할 수 있기 때문이다.

굳이 있을 때 1, 없을 때 0을 if문으로 구분하지 않아도 되며 무엇보다 시간복잡도가 O(n)으로 줄어든다. 

 

비트마스크는 알고리즘보다는 기술?에 가까운 것 같다. 이진수는 십진법으로 나타낼 수 있으며, true./false를 표현가능하므로 메모리를 많이 쓰는 array보다 훨씬 효율적이다. 이진수연산을 찾아서 하진 않았기 때문에 그냥 string과 for문을 이용했는데 이진수 연산 문제를 좀 더 풀어봐야할 것 같다. 좀 풀어놓으면 논설실에 도움이 되지 않을까!