백준 11723 집합

집합을 만드는 문제는 비트 마스크를 통해서 풀 수 있다.

만약 공집합에 1이라는 원소를 추가한다면 이는 0이라는 숫자의 1번 비트에 1을 추가하는 것과 같다.

따라서 집합을 나타내는 변수 ans가 있고, ans가 0이라고 하자.

ans |= (1 << 1) 과 같은 식은 공집합에 1이라는 원소를 추가하는 것과 같다.

ans의 값은 2가 될 것이다.(....00010)(1번 index에 1비트가 add된 것이다.)

ans를 집합으로 나타내면 {1}이 될 것이다.

즉, ans라는 값을 2진수로 나타내었을 때 비트가 1로 세팅된 index값이 ans 집합의 원소로 들어가는 것이다.

원소를 제거, toggle하는 방법 등은 아래의 코드에 나와있다.

 

문제를 풀면서 컴파일 에러가 발생했는데, strcmp함수를 사용하면서 cstring 헤더를 추가하지 않았기 때문이었다.

그리고 시간초과가 계속 발생했는데, cin 함수 대신 scanf함수를 사용하였더니 해결되었다.

앞으로 왠만하면 scanf함수와 printf함수를 사용하도록 해야겠다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
 
int main(int argc, char** argv) {
    int m, ans = 0;
    scanf("%d", &m);
 
    while (m--) {
        int num;
        char instruction[10];
        scanf("%s", instruction);
 
        if (!strcmp(instruction, "add")) {
            scanf("%d", &num);
            ans |= (1 << num);
        }
        else if (!strcmp(instruction, "remove")) {
            scanf("%d", &num);
            ans &= ~(1 << num);
        }
        else if (!strcmp(instruction, "check")) {
            scanf("%d", &num);
            if ((ans & (1 << num))) puts("1");
            else puts("0");
        }
        else if (!strcmp(instruction, "toggle")) {
            scanf("%d", &num);
            ans ^= (1 << num);
        }
        else if (!strcmp(instruction, "all")) {
            ans = (1 << 21) - 1;
        }
        else if (!strcmp(instruction, "empty")) {
            ans = 0;
        }
        else printf("error\n");
    }
 
    return 0;
}