[PS] 백준 11723번 집합

이번에는 백준 11723번 집합 문제를 풀어보았습니다.

문제를 처음 봤을 때 집합의 원소가 1부터 20까지만 존재한다는 점이 눈에 들어왔습니다.

원소의 개수가 매우 적기 때문에 하나의 정수를 이용하여 비트마스킹으로 집합을 표현할 수 있다고 생각했습니다.

각 연산을 비트 연산으로 구현하여 문제를 해결하였습니다.

---

문제 설명

공집합 S가 주어집니다.

다음 연산을 수행해야 합니다.

• add
• remove
• check
• toggle
• all
• empty

각 연산을 수행한 뒤 check 연산의 결과를 출력하는 문제입니다.

---

풀이 아이디어

집합의 원소는 1부터 20까지만 존재합니다.

따라서 하나의 int 변수의 비트를 이용하여 현재 집합을 표현하였습니다.

예를 들어

1 -> 1번째 비트
2 -> 2번째 비트
...
20 -> 20번째 비트

를 의미하도록 구현하였습니다.

각 명령은 비트 연산으로 처리하였습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;
int ret;

void solve(string s, int num) {
    if (s == "add") {
        ret |= (1 << num);
    } else if (s == "remove") {
        ret &= ~(1 << num);
    } else if (s == "check") {
        if (ret & (1 << num))
            cout << 1 << '\n';
        else
            cout << 0 << '\n';
    } else if (s == "toggle") {
        ret ^= (1 << num);
    } else if (s == "all") {
        for (int i=1; i<=20; i++) {
            ret |= (1 << i);
        }
    } else {
        ret = 0;
    }
}

int main() {

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

    int n;
    cin >> n;

    vector<pair<string,int>> inp;

    for (int i = 0; i < n; i++) {
        string s;
        int num;

        cin >> s;

        if (s == "all" || s == "empty") {
            inp.push_back({s, 0});
        } else {
            cin >> num;
            inp.push_back({s, num});
        }
    }

    for (int i = 0; i < n; i++) {
        solve(inp[i].first, inp[i].second);
    }

    return 0;
}

---

풀이 흐름

1. 명령을 입력받습니다.
2. 각 명령을 비트 연산으로 처리합니다.
3. check 명령인 경우 현재 비트를 확인하여 결과를 출력합니다.
4. 모든 명령을 수행한 뒤 프로그램을 종료합니다.

---

구현 포인트

1. add 연산

원소를 집합에 추가할 때는 OR 연산을 사용하였습니다.

ret |= (1 << num);

해당 비트를 1로 만들어 집합에 원소를 추가하였습니다.

---

2. remove 연산

원소를 제거할 때는 AND와 NOT 연산을 함께 사용하였습니다.

ret &= ~(1 << num);

해당 비트만 0으로 만들어 집합에서 제거하였습니다.

---

3. check 연산

현재 비트가 켜져 있는지 확인하였습니다.

if (ret & (1 << num))
    cout << 1 << '\n';
else
    cout << 0 << '\n';

비트가 1이면 집합에 존재하는 것이고, 0이면 존재하지 않는 것입니다.

---

4. toggle 연산

원소의 존재 여부를 반대로 바꾸기 위해 XOR 연산을 사용하였습니다.

ret ^= (1 << num);

비트가 1이면 0으로, 0이면 1로 변경됩니다.

---

5. all / empty 연산

all 명령은 모든 비트를 1로 만들었습니다.

for (int i=1; i<=20; i++) {
    ret |= (1 << i);
}

empty 명령은 집합을 비우기 위해 0으로 초기화하였습니다.

ret = 0;

이를 통해 모든 연산을 비트 연산만으로 처리할 수 있었습니다.