백준 11723 - 집합

C++

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

Set 사용

접근 방법

문제의 조건과 중복 되는 값을 허용하지 않는 자료구조인 Set이 적합 할 것이라 판단하여 set을 이용하여 구현하여 보았다.

구현

Set의 연산들을 사용해 보았으며, iterator를 이용해 찾고자 하는 값의 위치를 찾고 이를 통해 Erase기능도 구현하였다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;

int n;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	
	set<int> S;
	set<int>::iterator it;

	string order;
	int value;
	while (n--) {
		cin >> order;
		if (order == "add") {
			cin >> value;
			S.insert(value);
		}
		else if (order == "remove") {
			cin >> value;
			it = S.find(value);
			if (it == S.end())
				break;
			S.erase(it);
		}
		else if (order == "check") {
			cin >> value;
			it = S.find(value);
			if (it != S.end())			//해당하는 수가 있을 시
				cout << 1 << "\n";
			else
				cout << 0 << "\n";
		}
		else if (order == "toggle") {
			cin >> value;
			it = S.find(value);			// 해당하는 수가 있으면, 그 수의 위치를 반환한다.
			if (it != S.end())
				S.erase(it);			// 위에서 구한 위치로 Erase
			else
				S.insert(value);
		}
		else if (order == "all") {
			for (int i = 1; i <= 20; i++) {
				S.insert(i);
			}
		}
		else if(order == "empty"){
			S.clear();
		}
	}
	return 0;
}

Bit 연산

접근 방법

bit 연산을 통하여 더 빠른 방법으로도 접근하여 구하여 보았다.

구현

OR, AND, XOR 세 가지의 연산을 이용하였다.
1을 입력받은 value값 만큼 shift 연산을 하여 이동한다.
입력은 OR, 확인과 제거는 AND를 사용하였다.
toggle 입력은 XOR 연산을 사용하였는데, 이를 이용하면 간단히 구현 가능하다.
위 3가지의 비트 연산은 다음과 같은 참고 사진을 보면 이해가 빠르다.

all 입력은 20개의 1을 채워 넣으면 된다. 즉 [1111 1111 1111 1111 1111]로 만들면 되는데,
이는 [1 0000 0000 0000 0000 0000]에서 1을 빼면 되므로, 20개의 « 로 shift 연산을 한 뒤 1을 뺀다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, S;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;

	string order;
	int value;
	while (n--) {
		cin >> order;
		if (order == "add") {
			cin >> value;
			S |= (1 << value - 1);		// int의 처음 비트는 0 shift 이동이므로 1을 차감한 수 만큼 shift 연산을 한다.
		}
		else if (order == "remove") {
			cin >> value;
			S &= ~(1 << value - 1);
		}
		else if (order == "check") {
			cin >> value;
			if (S & (1 << value - 1))
				cout << 1 << "\n";
			else
				cout << 0 << "\n";
		}
		else if (order == "toggle") {
			cin >> value;
			S ^= (1 << value - 1);
		}
		else if (order == "all") {
			S |= (1 << 20) - 1;
		}
		else if(order == "empty"){
			S = 0;					// 0으로 만들어 버리면, 1이 없어지므로 S가 초기화 된다.
		}
	}
	return 0;
}

총평

난이도

⭐★★★★

후기

다들 다양하게 구현하였으며, 특히 bit 연산을 통하여 구현한게 눈에 띄었다.
Set을 쓰면 간단 해 질 수 있을거라 판단하였지만, 오히려 복잡하였으며 비트연산으로도 연습할 필요가 있다고 생각 된 문제였다.

개선할 점

없