[백준] 집합 11723번 (c++) 비트마스킹

출처 : https://www.acmicpc.net/problem/11723

 

풀이 방법

배열을 사용하여 풀이하는 방법도 있지만 비트를 사용한다면 더 빠르게 계산할 수 있다.

unsigned int s = 0;을 선언하고 각 연산을 s에 해준다.

 

add

n 자리에 or 연산을 통해 1비트를 기록한다.

s |= (1 << n); 

 

remove

n 자리에 0을 and연산하여 무조건 0으로 만들어 준다.

s &= ~(1 << n);

 

check

해당 비트에 1과 and연산을 하여 1이 된다면 1 출력 0이면 0을 출력한다.
s &  (1 << n)

 

toggle

해당 비트자리에 1과 xor연산을 하여 비어 있으면 채워 넣어주고 값이 있다면 제거해 주는 연산을 수행한다.
s ^= (1 << n);

 

all

21에서 1을 빼주면 비트는 20자리까지 모두 1로 채워진다. 즉 모든 값이 집합에 포함되어 있다고 해준다.
s = (1 << 21) - 1;

 

empty

s의 값을 0으로 설정하여 모든 비트 자리의 값을 0으로 설정하여 집합을 비운다.
s = 0

 

 

유의 점

endl보단 '\n'을 사용하자

endl은 버퍼를 비우는 동작이 실행되므로 단순히 줄 바꿈 문자만을 추가하는 '\n'보다 속도가 느리다.

 

    ios_base::sync_with_stdio(0);
    cin.tie(0);

c++, c의 표준 입출력 스트림의 동기화를 끊어 입출력 속도를 높여준다.

 

코드

 

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    unsigned int s = 0;

    int m, n;
    string cmd = "";

    cin >> m;

    for (int i = 0;i < m;i++) {
        cin >> cmd;        
        if (cmd == "add") {
            cin >> n;
            s |= (1 << n);
        }

        else if (cmd == "remove") {
            cin >> n;
            s &= ~(1 << n);
        }

        else if (cmd == "check") {
            cin >> n;
            if (s &  (1 << n)) {
                cout << 1 << '\n';
            }
            else {
                cout << 0 << '\n';
            }
        }

        else if (cmd == "toggle") {
            cin >> n;
            s ^= (1 << n);
        }

        else if (cmd == "all") {
            s = (1 << 21) - 1;
        }

        else if (cmd == "empty") {
            s = 0;
        }
    }

    return 0;
}