11723번: 집합

문제링크

CPP 코드

#include <iostream>
#include <cstring>

using namespace std;

int M;
int S;
string cmd, num;

void do_add(int &S)
{
    cin >> num;
    S |= (1 << (atoi(num.c_str()) - 1));
}

void do_remove(int &S)
{
    cin >> num;
    S &= ~(1 << (atoi(num.c_str()) - 1));
}

void do_check(int &S)
{
    cin >> num;
    if ((S & (1 << (atoi(num.c_str()) - 1))) > 0)
        cout << "1\n";
    else
        cout << "0\n";
}

void do_toggle(int &S)
{
    cin >> num;
    if ((S & (1 << (atoi(num.c_str()) - 1))) > 0)
    {
        S &= ~(1 << (atoi(num.c_str()) - 1));
    }
    else
    {
        S |= (1 << (atoi(num.c_str()) - 1));
    }
}

void do_all(int &S)
{
    S |= 0b11111111111111111111;
}

void do_empty(int &S)
{
    S &= 0;
}

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

    S = 0;
    cin >> M;
    for (int i = 1; i <= M; i++)
    {
        cin >> cmd;
        if (strcmp(cmd.c_str(), "add") == 0)
            do_add(S);
        else if (strcmp(cmd.c_str(), "remove") == 0)
            do_remove(S);
        else if (strcmp(cmd.c_str(), "check") == 0)
            do_check(S);
        else if (strcmp(cmd.c_str(), "toggle") == 0)
            do_toggle(S);
        else if (strcmp(cmd.c_str(), "all") == 0)
            do_all(S);
        else
            do_empty(S);
    }
}

어제 해시맵을 사용했던 터라 이번에도 해시맵으로 풀면 되나 했다(키-밸류 느낌이 들어서).
하지만 키의 갯수가 한정되어 있고 1부터 20까지 순차적으로 정해져있기 때문에 비트마스킹을 통해 풀 수 있겠다고 생각하고 처음으로 비트마스킹을 시도해보았다.

파이썬 코드

import sys
input = sys.stdin.readline

S = 0
M = int(input())
for i in range(1, M+1):
    arr = input().split()
    if arr[0] == 'add':
        S |= (1 << (int(arr[1]) - 1))
    elif arr[0] == 'remove':
        S &= ~(1 << (int(arr[1]) - 1))
    elif arr[0] == 'check':
        print(1 if (S & (1 << (int(arr[1]) - 1))) > 0 else 0)
    elif arr[0] == 'toggle':
        if S & (1 << (int(arr[1]) - 1)) > 0:
            S &= ~(1 << (int(arr[1]) - 1))
        else:
            S |= (1 << (int(arr[1]) - 1))
    elif arr[0] == 'all':
        S |= 0b11111111111111111111
    elif arr[0] == 'empty':
        S &= 0

같은 로직으로 파이썬으로 짜보았다.
파이썬은 print문 안에서 조건문을 사용할 수 있더라. 대신에 if문 전에 실행문이 나와야 된다는 점에 유의하자. 다중 if문도 가능하다고 한다.
input().split()을 통해 변수에 리스트로 넣어줄 수 있다. c나 cpp처럼 복잡하게 배열이나 벡터 선언 고민할 필요가 없는 점에서는 좋은 것 같다. 대신 여기서도 out of range를 참조하려 하면 문제가 생기니 주의하자.

다른 분들 풀이를 보니 'add', 'remove', 'toggle'에서 다음과 같이 작성하신 분들도 있었다.

...
  else:
    a = 1 << int(l[1]) - 1
    if (l[0] == 'add' and s & a == 0) or (l[0] == 'remove' and s & a) or l[0] == 'toggle':
      s ^= a

어떤 비트 k에 비트 1에 대해 xor연산을 수행하면 1) k가 1이면(있으면) 0, 2) k가 0이면(없으면) 1이 되므로 자연스럽게 토글이 된다.
다음에 비트를 바꿔주는 연산이 필요하게 되면 비트 1에 대해 xor연산을 써보도록 하자.
또 비슷하게 add명령 또한 비트가 0일때만으로 조건을 걸어주면 비트 1에 대한 xor연산으로 쓸 수 있고, remove 명령도 마찬가지.
따라서 세 가지 명령을 하나의 비트 연산으로 통일시킬 수 있게 된다.