[백준] 11723 집합 (C++)

 

문제 URL:

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

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

 

이 문제는 비트마스크를 사용하여 구현하는 문제였는데 쉬운 문제임에도 불구하고

비트마스킹 문제를 이전에 한 번도 접해보지 않아서 어렵게 느껴졌다.

비트마스크 연산은 다음과 같다. 

 

• And 연산 (&): 대응하는 두 비트가 모두 1이면 1 반환
  1010 & 1111 = 1010
• OR 연산 ( | ): 대응하는 두 비트 중 하나라도 1이면 1 반환
  1010 & 1111 = 1111
• Shift 연산 («,») : 비트를 왼쪽 또는 오른쪽으로 한칸씩 이동
  0011 « 2 = 1100
  1010 » 1 = 0101
• XOR 연산 (^): 대응하는 두 비트가 다르면 1 같으면 0 반환
  1010 ^ 1100 = 0110
• Not 연산 (~) : 비트를 반전
  ~1111 = 0000

1부터 20까지 존재할 수 있는 집합 S를 int형 변수 BIT로 생각하고,

비트마스크 연산을 이용하여 문제에서 수행해야할 연산(add, remove, check, toggle, all, empty)을 수행한 코드는 아래와 같다.

(주석 예시 확인)

---

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

int M;
string op;
int num, BIT = 0; // BIT를 반드시 0으로 초기화

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

	cin >> M;

	while (M--) {
		cin >> op;

		if(op == "add") {
			cin >> num;
			// or 연산을 통해 num번째 자릿수를 1로 채움
			BIT |= (1 << num);  // if num == 1 {0001 -> 0010}
		}
		else if (op == "remove") {
			cin >> num;
			// and 연산을 통해 num번째 자릿수를 0으로 바꿔줌
			BIT &= ~(1 << num);  // if num == 1 {0001 -> 0010 -> 1101}
		}
		else if (op == "check") {
			cin >> num;
			// and 연산을 통해 num번째 자릿수에 1이 있는지 확인
			if (BIT & (1 << num))  // if BIT == 1110 & num == 1 {1110 & 0010 -> 0010}
				cout << 1 << '\n';
			else                   // if BIT == 1100 & num == 1 {1100 & 0010 -> 0000}
				cout << 0 << '\n';
		}
		else if (op == "toggle") {
			cin >> num;
			// xor 연산을 통해 num번째 자릿수를 1 또는 0으로 변경
			BIT ^= (1 << num); 
			// if BIT == 1110 & num == 1 {1110 ^ 0010 -> 1100}
			// if BIT == 1100 & num == 1 {1100 ^ 0010 -> 1110}
		}
		else if (op == "all") {
			BIT = (1 << 21) - 1;  // ex. 10000 - 1 = 1111
		}
		else if (op == "empty") {
			BIT = 0;
		}
	}

	return 0;
}

 

참고: https://donggoolosori.github.io/2020/09/24/boj-11723/