[Java] BOJ 11723: 비트마스크 (BitMask)

---

들어가기에 앞서

 

 비트마스크란 컴퓨터의 비트를 이용해, 이진 데이터로 상태를 저장하고 처리하는 기법이다. 작은 메모리 공간으로 다양한 연산을 수행할 수 있기에 효율적인 알고리즘을 설계할 수 있다. 주로 플래그 설정, 집합의 요소 추적, 특정 비트에 대한 연산 등에 사용된다.

---

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Problem11723 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int m = Integer.parseInt(br.readLine());
        HashSet<Integer> set = new HashSet<>();

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());

            String option = st.nextToken();
            int value = 0;

            if (!option.equals("all") && !option.equals("empty")) {
                value = Integer.parseInt(st.nextToken());
            }

            switch (option) {
                case "add":
                    set.add(value);
                    break;
                case "remove":
                    set.remove(value);
                    break;
                case "check":
                    if (set.contains(value)) {
                        System.out.println(1);
                    } else {
                        System.out.println(0);
                    }
                    break;
                case "toggle":
                    if (set.contains(value)) {
                        set.remove(value);
                    } else {
                        set.add(value);
                    }
                    break;
                case "all":
                    for (int i = 1; i <= 20; i++) {
                        set.add(i);
                    }
                    break;
                case "empty":
                    set.clear();
                    break;
            }
        }
    }
}

▶ HashSet을 사용해 풀었지만 결과는 시간 초과로 인한 실패다.

---

---

 비트마스크 사용은 공간복잡도와 시간복잡도 측면에서 이점을 가진다.

 

 비트마스크는 1개의 정수로 모든 집합을 표현할 수 있어, HashSet 대비 메모리 사용이 효율적이다. 또한, 비트 연산은 매우 빠르기 때문에 각 연산의 시간복잡도는 모두 O(1)로 처리되어 시간복잡도 측면에서도 우위를 가진다.

 

 이번 집합 문제처럼 고정된 범위 (1부터 20까지) 일 때, 우리는 비트마스크를 사용해 볼 수 있다.

---

 비트마스크의 기본 연산자는 크게 4가지이고, 추가로 2가지를 더 알고 있으면 좋다.

 

1. & (비트 AND): 두 비트가 모두 1일 때 1을 반환한다.

2. | (비트 OR): 두 비트 중 하나라도 1이면 1을 반환한다.

3. ^ (비트 XOR): 두 비트가 다를 때 1을 반환한다.

4. ~ (비트 NOT): 비트를 반전시킨다.

5. << (비트 왼쪽 이동): 비트를 왼쪽으로 이동시킨다.

6. >> (비트 오른쪽 이동): 비트를 오른쪽으로 이동시킨다.

 

 이제 문제로 돌아가자.

 (참고로 본 문제에서는 입력되는 수가 20까지로 제한되기 때문에 32비트를 갖는 int 자료형으로 설정했다.)

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int S = 0;
        int M = Integer.parseInt(br.readLine());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            if (command.equals("add")) {
                int value = Integer.parseInt(st.nextToken());
                S |= (1 << value);
            }
            else if (command.equals("remove")) {
                int value = Integer.parseInt(st.nextToken());
                S &= ~(1 << value);
            }
            else if (command.equals("check")) {
                int value = Integer.parseInt(st.nextToken());
                sb.append((S & (1 << value)) != 0 ? 1 : 0).append("\n");
            }
            else if (command.equals("toggle")) {
                int value = Integer.parseInt(st.nextToken());
                S ^= (1 << value);
            }
            else if (command.equals("all")) {
                S = (1 << 21) - 1;
            }
            else if (command.equals("empty")) {
                S = 0;
            }
        }
        System.out.print(sb);
    }
}

int 자료형 S을 선언하고 0을 넣어주면, 아래와 같은 모습이다.
int S = 0000 0000 0000 0000 0000 0000 0000 0000 (이해를 돕기 위한 표현)
※ 각 자리수를 0부터 31까지의 비트 인덱스 그대로 이해하면 된다.

---