[백준] 11723 집합 JAVA

 

분석

---

비트마스킹을 이용하여 푸는 문제이다.

 

비트마스킹이란?

- 컴퓨터는 모든 자료를 이진수로 표현하는데, 이를 이용하여 자료구조로 쓰는 기법이다.

  비트마스킹을 통해 스위치,방문 처리 등 다양한 문제를 해결할 수 있다.

  

 

비트연산자의 종류

- 비트마스크의 상태를 변경시키기 위해 다양한 비트 연산자를 활용할 수 있다.

 

1.  a | b

    - a의 모든 비트와 b의 모든 비트를 OR 연산을 수행한다.

    ex) a=1 , b=1 일때 a | b = 1

          a=1 , b=0 일때 a | b = 1

          a=0 , b=0 일때 a | b = 0

 

2.  a & b

    - a의 모든 비트와 b의 모든 비트를 AND 연산을 수행한다.

    ex) a=1 , b=1 일때 a & b = 1

          a=1 , b=0 일때 a & b = 0

          a=0 , b=0 일때 a & b = 0

 

3.  a ^ b

     - a의 모든 비트와 b의 모든 비트를 XOR 연산을 수행한다. (다르면 1 , 같으면 0)

    ex) a=1 , b=1 일때 a ^ b = 0

          a=1 , b=0 일때 a ^ b = 1

          a=0 , b=0 일때 a ^ b = 0

 

4.  ~a

      - a의 모든 비트에 NOT 연산을 한다.

 

5.  a << b OR a >> b

       - a의 비트를 왼쪽(오른쪽)으로 b만큼 쉬프트한다.

         ex) 1 << 2 : 2의 2승

               1 << 0 : 2의 0승 

 

위의 연산자들을 응용하여 더 다양한 연산을 수행할 수 있다.

 

1.idx번째 비트 켜기

   S |= (1<<idx)

 

2. idx번째 비트 끄기 

    S &= ~(1<<idx)

 

3. idx에 대한 XOR 연산

    S ^= (1<<idx)

 

4. 최하위 켜져있는 idx 찾기

     idx = (S & -S)

     * -S = (~S+1) 의 특성을 가지기 때문에 가능하다.

      ex ) S = 1010 , ~S = 0101

             -S = 0101 + 1

                  = 0110

              S & -S = 2(마지막 인덱스)

 

5. n인 모든 집합의 비트 켜기

     (1<<n) - 1

 

6. idx번째 비트가 있는 지 확인하기

    if(S & (1 << idx)) 

     

이 개념들을 숙지하면 위의 문제를 풀 수 있다 !

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Math.abs;

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int bit=0;
        for(int i=0;i<num;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int seq=0;

            switch (st.nextToken()){
                case "add":
                   seq = Integer.parseInt(st.nextToken());
                   bit |= (1<<(seq-1));
                   break;
                case "remove":
                    seq = Integer.parseInt(st.nextToken());
                    bit &= ~(1<<(seq-1));
                    break;
                case "check":
                    seq = Integer.parseInt(st.nextToken());
                    sb.append((bit & (1<<(seq-1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle":
                    seq = Integer.parseInt(st.nextToken());
                    bit ^= (1 << (seq-1));
                    break;
                case "all":
                    bit |= (~0);
                    break;
                case "empty":
                    bit &= 0;
                    break;
            }
        }
        System.out.println(sb);
    }


}