[JAVA] 11723 - 집합 🩶5 : 집합 여부를 Set 자료구조가 아닌 비트마스킹으로 풀어보기

들어가며

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

문제 이해는 크게 어렵지 않다. 마치 Set 자료구조에 존재하는 메서드를 구현하라는 것과 같다.

본문으로

나는 처음에는 부담없이 아래와 같이 Set 자료구조를 이용하여 풀이를 제출했다.

public class Main {

    static int M;
    static Set<Integer> set;
    static StringBuilder sb;

    static void add(int x) {
        set.add(x);
    }

    static void remove(int x) {
        set.remove(x);
    }

    static void check(int x) {
        if (set.contains(x)) {
            sb.append("1").append("\n");
        } else {
            sb.append("0").append("\n");
        }
    }

    static void toggle(int x) {
        if (set.contains(x)) {
            set.remove(x);
        } else {
            set.add(x);
        }
    }

    static void all() {
        for (int i = 1; i <= 20; i++) {
            set.add(i);
        }
    }

    static void empty() {
        set.clear();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        M = Integer.parseInt(bf.readLine());
        set = new HashSet<>();
        sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            String oper = st.nextToken();
            if (oper.equals("all")) {
                all();
                continue;
            }
            if (oper.equals("empty")) {
                empty();
                continue;
            }
            int x = Integer.parseInt(st.nextToken());
            if (oper.equals("add")) {
                add(x);
            } else if (oper.equals("remove")) {
                remove(x);
            } else if (oper.equals("check")) {
                check(x);
            } else if (oper.equals("toggle")) {
                toggle(x);
            }
        }

        System.out.println(sb);
    }
}

정답은 어렵지 않게 제출할 수 있었다. 근데 다른분들의 풀이를 참고하다가, 비트마스킹 기법으로도 푸는 코드를 많이 보았다. 코드를 확 줄일 수 있고, 매우 직관적이라 코드를 정리하고자 한다.

---

아래는 비트마스킹 풀이이다 자세한 풀이는 주석으로 친절하게 달아두었다.

public class Main {

    static int N, M;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = 0;
        M = Integer.parseInt(bf.readLine());
        sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            String oper = st.nextToken();
            if (oper.equals("all")) { // "all"은 1~20포함
                N = (1 << 21) - 1;
                continue;
            }
            if (oper.equals("empty")) { // "empty"는 0으로
                N = 0;
                continue;
            }
            int x = Integer.parseInt(st.nextToken());
            if (oper.equals("add")) { // "add"는 OR연산자를 활용하여 추가하고자 하는 비트를 켜서 집합에 포함시킨다.
                N |= (1 << x);
            } else if (oper.equals(
                    "remove")) { // "remove"는 지우고자 하는 비트를 켠다음(00100) 반전시킨 시킨 후(11011) AND연산자를 통해 집합에서 제외시킨다.
                N &= ~(1 << x);
            } else if (oper.equals("check")) { // "check"는 찾고자 하는 비트를 켜서 AND연산자를 통해 포함되어있는지 판단한다.
                if (((N & (1 << x)) != 0)) {
                    sb.append("1").append("\n");
                } else {
                    sb.append("0").append("\n");
                }
            } else if (oper.equals("toggle")) { // "toggle"은 찾고자 하는 비트를 켜서 XOR연산자를 통해 있으면 없애고, 없으면 추가한다.
                N ^= (1 << x);
            }
        }
        System.out.println(sb);
    }
}

메모리나 시간복잡도는 비슷하다.

코드를 길이가 매우 짧아지지 않았는가?! 그리고 수행하고자 하는 비트를 켜서 비트연산자로 집합의 행위를 흉내낼 수 있다는 점이 매우 인상적이다.

마무리하며

비트마스킹 풀이를 경우의 수 뽑아낼 때만 쓸 줄 알았는데, 이렇게 Set자료구조를 대신할 수 있다는 점이 매우 인상적이었다. 앞으로도 비트연산자 잘 이용해봐야겠다. 꾸준하게 잘 가보자!!!