[백준] 11723번 : 집합

문제

 

---

풀이

 

비트연산과 관련된 문제이다.

여기저기에서 배운거라 개념은 잘 알지만 막상 문제를 풀어보려니까 살짝 당황한건 사실이다.

 

S에 들어올 수 있는 값을 7까지로 제한하도록 하겠다.

S = 0이라고 하고 이걸 8자리의 2진수로 표현해보면

 

0000 0000 이다. 여기부터 시작하자.

 

add 3을 한다고 하자.

1<<3을 하면 0000 1000이 된다. 이걸 S와 or 연산하면

0000 0000 | 0000 1000 = 0000 1000 이다. 이렇게 add가 됐다.

 

remove 3을 한다고 하자.

아까처럼 1<<3을 하는데 이걸 ~(1<<3)으로 뒤집으면 1111 0111이 된다. 이걸 S와 and 연산하면

0000 1000 & 1111 0111 = 0000 0000 이다. 이렇게 remove가 됐다.

 

check 3을 한다고 하자.

이번엔 뒤집지 않은 그냥 1<<3과 S를 and 연산한다.

만약 3이 있었다면 and 연산으로도 값이 남아서 S가 0이 되지 않겠지만 그렇지 않다면 0이 될 것이다.

0000 0000 & 0000 1000 = 0000 0000 이다. 이렇게 check를 확인한다.

 

toggle 3을 한다고 하자.

이번엔 xor 연산을 사용할 것이다. xor 연산은 두 비트가 같다면 0을 반환하고 다르다면 1을 반환한다.

0000 0000 ^ 0000 1000 = 0000 1000 이다. 이렇게 toggle이 됐다.

 

all 연산은 최댓값에서 1을 빼주면 된다.

들어올 수 있는 값을 7로 제한한 상황에선 (1<<8) -1을 하면된다.

 

empty 연산은 그냥 S를 0으로 만들면 된다.

---

소스코드

 

#include <iostream>
#include <string>
#include <bitset>

using namespace std;

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

    int M, num;
    string input;
    int S = 0;

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> input;
        if (input.compare("add") == 0) {
            cin >> num;
            S |= 1 << num; // or 연산
        } else if (input.compare("remove") == 0) {
            cin >> num;
            S &= ~(1 << num); // reverse and 연산
        } else if (input.compare("check") == 0) {
            cin >> num;
            int tmp = S & (1 << num); // and 연산해서 0이 아니면 1 반환
            if (tmp)
                cout << 1 << '\n';
            else
                cout << 0 << '\n';
        } else if (input.compare("toggle") == 0) {
            cin >> num;
            S ^= 1 << num; // xor 연산
        } else if (input.compare("all") == 0)
            S = (1 << 21) - 1; //최댓값에서 1을 뺌
        else if (input.compare("empty") == 0)
            S = 0; //0으로 초기화
    }
}