백준 11723번: 집합

1.문제

2.예제

all : 1~20의 모든 원소를 집합 S에 추가.

check: check가 입력될 때마다 해당 원소를 포함하고 있으면 1을, 그렇지 않으면 0을 출력한다.

※'&' 연산 사용시 주의

a & (1 << b) //  연산 결과는 0 또는 (1<<b)가 나온다.

'&'연산자의 결과는 1 또는 0이 아니라, 0 또는 두 번째 operand인 shifting한 비트이다.

따라서 if( ( a& (1<<b) ) == 1) 과 같은 조건식을 작성하지 않도록 주의하자.

3.해제

집합에 해당 원소가 있는지, 없는지 확인만하면 되므로 비트마스크를 이용하자.

최대 연산의 수가 3,000,000이기 때문에 처음에 시간초과가 나왔다.

따라서 아래와 같이 cin,cout 가속이 필요하다.
(※ 싱글 스레드에서만 사용해야 하며, printf, scanf와 섞어 쓰면 안 된다.)

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

처음에 입력이 끝까지 되지 않는 문제가 있었는데, 알고보니 all과 empty은 추가로 입력을 받지 않는데 cin 받아서 입력이 중간에 끊겼었다.

전체 코드는 아래와 같다.

#include <iostream>
#include <string>

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

    int n;
    int init_S = 0;

    cin >> n;

    while (n--)
    {
        int input;
        string command;
        cin >> command;

        if (command != "empty" && command != "all")
        {
            cin >> input;
        }

        if (command == "add")
        {
            init_S |= (1 << input);
        }
        else if (command == "check")
        {
            bool ans;

            if (init_S & (1 << input))
                ans = true;

            else
                ans = false;

            cout << ans << '\n';
        }
        else if (command == "remove")
        {
            init_S &= ~(1 << input);
        }
        else if (command == "toggle")
        {
            init_S ^= (1 << input);
        }
        else if (command == "all")
        {
            init_S = ((1 << 21) - 1);
        }
        else if (command == "empty")
        {
            init_S = 0;
        }
    }
}