[BOJ/비트] 백준 11723 - 집합 (Java)

11723 - 집합

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

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램
- add x: S에 x 추가
- remove x: S에서 x 제거
- check x: S에 x가 있으면 1/ 없으면 0 출력
- toggle x: S에 x가 있으면 x를 제거/ 없으면 0 출력
- all: S를 {1, 2, ..., 20}으로 바꿈
- empty: S를 공집합으로 바꿈
(1 <= x <= 20)

입력
첫째 줄: 수행해야 하는 연산의 수 M (1 <= M <= 3,000,000)
둘째 줄 ~ M개의 줄: 수행해야 하는 연산
출력: check 연산 주어질때마다, 결과 출력

---

풀이

숫자 1 ~ 20 저장

전등 켜져 있으면 숫자가 집합에 있음 / 꺼져 있으면 집합에 없음

ex. {1, 3} -> 전등 상태: 1(3) 0(2) 1(1) => 2진수: 101 / 10진수: 5

-> 숫자 하나로 집합 표현

• `1 << x`: 1을 왼쪽으로 x칸 이동 => $2^x$
  
  • x번째 전등 하나만 켠 숫자
    • ex. 1 << 3 = 00001000 => 3번 전등만 켜짐
• ex. 1 << 0 = 00000001 (1) / 1 << 1 = 00000010 (2)
  / 1 << 2 = 00000100 (4) / 1 << 3 = 00001000 (8)

 

• add: `set |= (1 << x)`
  • `|`: OR
  • 이미 켜져 있으면 그대로 유지/ 꺼져 있으면 켜짐
• remove: `set &= ~(1 << x)`
  • ~: NOT / `&`: AND
  • 그 전등만 켜진 상태 만들고 뒤집기 = 그 전등만 꺼져 있고 나머지 켜짐
    + AND -> 그 번호 비트가 꺼짐
• check: `(set & (1 << x)) != 0`
  • `&`: AND
  • 0이 아니면 비트 켜져 있음
• toggle: `set ^= (1 << x)`
  • `^`: XOR -> 1 ^ 1 = 0 / 0 ^ 1 = 1 => 비트 반전
  • 켜져 있으면 끄고 꺼져 있으면 켬
• `all`: `set = (1 << 21) - 2`
  • 1 ~ 20만 사용 -> 1 << 21 = 1000000000000000000000
    -> -1하면 0111111111111111111111/ -2하면 0111111111111111111110
    => 1 ~ 20번 비트만 1

---

코드

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

// 집합
public class boj_11723 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(br.readLine());

        int set = 0;
        while (M-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();

            if (cmd.equals("add")) {
                int x = Integer.parseInt(st.nextToken());
                set |= (1 << x);
            } else if (cmd.equals("remove")) {
                int x = Integer.parseInt(st.nextToken());
                set &= ~(1 << x);
            } else if (cmd.equals("check")) {
                int x = Integer.parseInt(st.nextToken());
                sb.append((set & (1 << x)) != 0 ? 1 : 0).append("\n");
            } else if (cmd.equals("toggle")) {
                int x = Integer.parseInt(st.nextToken());
                set ^= (1 << x);
            } else if (cmd.equals("all")) {
                set = (1 << 21) - 2;
            } else if (cmd.equals("empty")) {
                set = 0;
            }
        }

        System.out.print(sb);
    }
}