실제 코딩테스트를 많이 경험하진 못했지만, 비트마스킹 문제가 DFS/BFS 못지 않게 빈출 유형인 거 같아서 익혀둬야겠다는 생각이 들었다.

그래서 풀어본 완전 기본 문제.
사실 비트마스킹에 대한 개념이 거의 없었다고 봐도 무방해서, 간단하게 개념만 보고 풀이하였다.

집합의 표현

비트마스크를 사용하면 집합을 쉽게 표현할 수 있고, 원소 추가, 삭제를 굉장히 빠르게 수행할 수 있다.

원소의 개수가 N인 집합이 있을 때, 각 원소를 0번부터 (n-1)번까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 존재, 0이면 존재하지 않는 것이다.

예를 들어 s = {1, 3, 4, 5} 집합이 있다고 가정하자.
비트마스크로 표현하면, 111010(2)로 표현할 수 있다.

$2^1 + 2^3 + 2^4 + 2^5 = 111010_2$

아래의 표를 참고하면 더 이해하기 쉬울 것이다.

5	4	3	2	1	0
1	1	1	0	1	0

비트마스크의 연산

1. 원소 추가
   s = s | (1 << p)
   p번 비트만 1, 나머지 비트는 0인 값으로 만들고 |연산(or)을 진행하면 p번 비트는 1로 바뀌게 되고 나머지는 원래 상태를 유지한다.
2. 원소 삭제
   s = s & ~(1 << p)
   마찬가지로 p번 비트만 1, 나머지 비트는 0으로 만들고, ~연산을 통해 p번 비트만 0, 나머지 비트는 1로 만든 후 &연산을 진행하면 p번만 0으로 바뀌고, 나머지는 현재 상태와 동일하게 유지된다.
3. 원소 토글
   p번 비트가 1이면 0으로, 0이면 1로 바꾸는 연산을 의미한다.
   s = s ^(1 << p)
   마찬가지로 p번 비트만 1, 나머지 비트는 0으로 만들고, s의 나머지 비트들은 XOR 연산을 진행하므로 0이면 0, 1이면 1로 현재 상태를 유지하고 p번 비트는 1과 XOR 연산을 진행하므로 1이면 0, 0이면 1로 토글된다.
4. 원소 존재 확인
   s & (1 << p)
   마찬가지로 p번 비트만 1, 나머지 비트는 0으로 만들고, &연산을 진행하면 p번 비트가 1이라면 0보다 큰 정수를, 0이라면 0을 반환한다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol11723 {
    static int m;
    static int s = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        m = Integer.parseInt(br.readLine());

        while (m > 0) {
            m--;
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            int num;
            if (cmd.equals("add")) {
                num = Integer.parseInt(st.nextToken()) - 1;
                s |= (1 << num);    //  추가(비트 on)
            } else if (cmd.equals("remove")) {
                num = Integer.parseInt(st.nextToken()) - 1;
                s &= ~(1 << num);   //  삭제(비트 off)
            } else if (cmd.equals("check")) {
                num = Integer.parseInt(st.nextToken()) - 1;
                bw.write((s & (1 << num)) != 0 ? "1" : "0");
                bw.newLine();
            } else if (cmd.equals("toggle")) {
                num = Integer.parseInt(st.nextToken()) - 1;
                s ^= (1 << num);
            } else if (cmd.equals("all")) {
                for (int i = 0; i < 20; i++) {
                    s |= (1 << i);
                }
            } else if (cmd.equals("empty")) {
                s = 0;
            }
        }
        bw.flush();
        bw.close();
    }
}