[백준] 11723번 : 집합 - JAVA [자바]

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

---

boolean 배열을 사용해도 되지만 비트마스크 기법을 사용하면 메모리를 더욱 더 효율적으로 사용할 수 있다.

비트마스킹 기법에 대해서는 이 포스팅을 보고 오자

집합에서 가장 큰 수는 20 이다.
즉, 이진수 20자리 = 20 bit 로 표현이 가능하다.
int 형 자료형은 4바이트(4 * 8bit = 32bit)까지 표현이 가능하므로 int a = 0;으로 32 개의 집합의 부분 집합을 나타낼 수 있다.

각 구문에 맞춰 switch 문을 구현해 주면 된다.

일단 각 자리를 표현하는 방법만 알면 해결하기 쉽다.

1 << 10 이란 1을 왼쪽으로 10 자리 옮긴 수 이다.
즉, 이진수로 나타내면 10000000000(2) 이다.

add 10을 예로 들어보자 현재 부분집합을 나타내는 자료구조로 a를 사용하고 있으므로 a = a | (1<<10) 으로 a의 10 번째 숫자가 1이 되도록 할 수 있다.
10 번째가 1이라는 것은 이 부분 집합에 10이 포함되어 있다는 것이다.

여기서 주의할 점이 있는데, a가 100이라고 생각해보자. 그러면 a는 10진수로 8이다.
즉, 여기서 a & (1<<2) 은 1이 아니고 8이 된다.
하지만 a가 000이면 0이 나오므로 숫자가 포함 되어 있는지 확인할 때 1==을 사용하지 말고 0<을 사용하자.

---

public class bj117233 {

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

        // 20이 집합에 있을 수 있는 가장 큰 수이다.
        // 즉 21비트 짜리 정수로 표현할 수 있다.
        // int 자료형은 4바이트 (8bit * 4 = 32bits) 이므로
        // int 자료형 변수 하나를 선언한다.

        int a = 0;

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            String[] split = line.split(" ");
            switch (split[0]) {
                case "add": {
                    a = a | (1 << Integer.parseInt(split[1]));
                    break;
                }
                case "check": {
                    if (0 < (1 << Integer.parseInt(split[1]) & a)) {
                        bw.write(1 + "\n");
                    } else {
                        bw.write(0 + "\n");
                    }
                    break;
                }
                case "remove": {
                    a = a & ~(1 << Integer.parseInt(split[1]));
                    break;
                }
                case "toggle": {
                    if (0 < (1 << Integer.parseInt(split[1]) & a)) {
                        a = a & ~(1 << Integer.parseInt(split[1]));
                    } else {
                        a = a | (1 << Integer.parseInt(split[1]));
                    }
                    break;
                }
                case "all": {
                    a = a | (1 << 21) - 1;
                    break;
                }
                case "empty": {
                    a = 0;
                    break;
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }

}