[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. >> (비트 오른쪽 이동): 비트를 오른쪽으로 이동시킨다.

 

 이제 문제로 돌아가자.

---

아직 못 풀었어요.

---