백준[11723] 집합

문제 설명

풀이

집합을 아래와 같이 비트로 표현 할 수 있다.

{1, 2, 3, 4, 5} -> 11111

{2, 3, 4, 5} -> 11110

{1, 3, 5} -> 10101  

 

i 번째 비트만 1로 바꾸기 == or 연산

set = set | (1 << (i -1));

ex) i = 2 일때, 0000 | (1 << 1 )  ->  0000 | 0010   -> 0010 

 

i 번째 비트만 0로 바꾸기 == and 연산

set = set & ~(1 << (i -1));

ex) i = 2 일때, 1111 & (1 << 1 )  ->  1111 & ~0010   -> 1111 & 1101 -> 1101

 

i 번째 비트만 뒤집기 == xor 연산

set = set ^ (1 << (i -1));

ex) i = 2 일때, 1111 ^ (1 << 1 )  ->  1111 ^ 0010   ->  1101

 

i 번째 비트가 1인지 0인지 확인

set & 1 << (i - 1);

ex) 1100 & (1 << 2) -> 1100 & 0100 -> 0100 -> 결과값 != 0 -> i번째 비트가 1

 

코드

#include <cstdio>
#include <string>

using namespace std;

int main() {
    int M; scanf("%d", &M);
    int set = 0;
    while (M--) {
        char tmp[10]; scanf("%s", tmp);
        string input = tmp;
        if (input == "add") {
            int num; scanf("%d", &num);
            set |= (1 << (num - 1));
        } else if (input == "remove") {
            int num; scanf("%d", &num);
            set &= ~(1 << (num - 1));

        } else if (input == "check") {
            int num; scanf("%d", &num);
            printf("%d\n", set & (1 << (num - 1)) ? 1 : 0);
        } else if (input == "toggle") {
            int num; scanf("%d", &num);
            set ^= (1 << (num - 1));
        } else if (input == "all") {
            set = 0xfffff;// 1111 1111 1111 1111 1111
        } else if (input == "empty") {
            set = 0; // 0000 0000 0000 0000 0000
        }
    }
}