[백준 11723] 집합 / 자바 / 비트마스킹

문제         

레벨: S5
알고리즘: 비트마스킹
풀이시간: 20분
힌트 참조 유무: 유

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

 

1 번째 시도   

 

[비트마스킹]

모든 자료형를 이진수로 표현하는 것.
 더 빠른 시간과, 더 적은 메모리 사용

[비트 연산자]

a&b   a와b 둘다 1이어야 1
a|b    a와b 둘 중 하나라도 1이면 1
a^b   a와b가 다르다면 1
~a    0 -> 1,  1 -> 0
a<<b    b비트만큼  좌측으로 자리이동
a>>b     b비트만큼 우측으로 자리이동

[집합의 표현]

비트의 각 자리수
1: 존재한다.
0: 존재하지 않는다.

즉 아래와 같다.

{A,B,C,D,E,F}

{A} = 100000

{A,F} = 100001

 

[로직 설명]

boolean배열로도 원소가 있다 없다를 표시할 순 있지만, 메모리 제한이 생긴다.

그래서 우리는 비트마스킹을 사용하는 거다.

 

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
       int n = Integer.parseInt(br.readLine());
       int bitset = 0;

       while(n-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            int num;

            // 수행연산
            switch (op){
                case "add" :
                    num = Integer.parseInt(st.nextToken());
                    bitset |= (1 << (num - 1));
                    break;
                case "remove" :
                    num = Integer.parseInt(st.nextToken());
                    bitset = bitset & ~(1 << (num - 1));
                    break;
                case "check" :
                    num = Integer.parseInt(st.nextToken());
                    sb.append((bitset & (1 << (num - 1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle" :
                    num = Integer.parseInt(st.nextToken());
                    bitset ^= (1 << (num - 1));
                    break;
                case "all" :
                    bitset |= (~0);
                    break;
                case "empty" :
                    bitset &= 0;
                    break;
            }
        }
        bw.write(sb.toString());
        bw.close();
        br.close();
    }
}