[백준] 집합 (11723) (java)

문제

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

11723번: 집합

문제접근

처음 문제를 접하자마자 boolean 배열을 선언하여 각 숫자마다 True, False 를 두고 문제를 풀려고하였습니다.

하지만 비트마스크의 개념을 공부한 뒤, 새로운 접근법에대해 생각해볼 수 있었습니다.

 

비트마스크란 간단히 bit로 표시를 해둔다고 이해하면 쉽게 이해할 수 있습니다.

 

해당 문제를 예시로 들어보면, boolean 배열로 add 1, add 3, add 4 는 어떻게 표현될까요 ?

(문제의 입력 조건을 보면 x는 1이상 이므로 배열의 0번째를 숫자1로 매핑해도 됩니다.)

arr[0]=true , arr[2]=true, arr[3]=true 

즉,

{true, false, true, true, false, false,......} 로 표현될 수 있습니다.

이걸 이진수로 표현하면 1101(십진수 13) 이렇게 됩니다.

그렇다면 다시 add 1, add 2, add 3, add 4 를하면 이진수로 1111(십진수 15) 로 표현할 수 있습니다.

 

결국 하나의 숫자로 어떤 숫자가 add 됬는지 알 수 있게됩니다.

 

다시 처음으로 boolean 배열을 사용하면 20까지의 숫자유무를 판단하기위해 Integer * 20 만큼의 메모리를 사용했다면

비트마스크로 접근하면 Integer 하나만큼의 메모리로 문제를 해결할 수 있습니다. 메모리적으로 아주 훌륭한 접근법이라고 생각합니다.

 

코드를 보고 잘 이해가 가지않는다면, 비트 연산을 공부한 뒤 풀이하시면 쉽게 풀 수 있습니다.

 

코드

package BitMasking;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Set {
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(br.readLine());
        int bitMask =0;
        while(M-- >0){
            String s = br.readLine();
            StringTokenizer st = new StringTokenizer(s," ");
            String op = st.nextToken();
            int n;

            switch (op){
                case "add":
                    n = Integer.parseInt(st.nextToken());
                    bitMask = bitMask | 1<<(n-1);
                    break;

                case "remove":
                    n = Integer.parseInt(st.nextToken());
                    bitMask = bitMask & ~(1<<(n-1));
                    break;

                case "check":
                    n = Integer.parseInt(st.nextToken());
                    sb.append(((bitMask & 1<<(n-1)) == 1<<(n-1) ? 1:0)+"\n");
                    break;

                case "toggle":
                    n = Integer.parseInt(st.nextToken());
                    bitMask = bitMask ^ 1<<(n-1);
                    break;

                case "all":
                    bitMask = ~0;
                    break;

                case "empty":
                    bitMask = 0;
                    break;

            }
        }
        bw.write(sb.toString());
        bw.close();
        br.close();

    }
}

 

깃허브: https://github.com/jsh9057/Algorithm/blob/master/src/BitMasking/Set.java

jsh9057/Algorithm