11723 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

check 연산이 주어질때마다, 결과를 출력한다.

예제 입력 1

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

코드

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

public class P_11723 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int bit = 0;

        for (int i = 0; i < n; i++) {
            String[] calc = br.readLine().split(" ");

            switch (calc[0]) {
                case "add" :
                    bit |= (1 << Integer.parseInt(calc[1]));
                    break;
                case "remove" :
                    bit &= ~(1 << Integer.parseInt(calc[1]));
                    break;
                case "check" :
                    bw.write((bit & (1 << Integer.parseInt(calc[1]))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle" :
                    bit ^= (1 << Integer.parseInt(calc[1]));
                    break;
                case "all" :
                    bit |= ~(0);
                    break;
                case "empty" :
                    bit &= 0;
                    break;
            }
        }
        bw.flush();
    }
}

코드 설명

메모리 제한과 시간 제한 때문에 비트마스크를 이용했다.

비트마스크는 비트의 &, | 연산을 이용하는 것인데 문제에 0은 들어오지 않지만 다른 문제에 0이 들어올 것을 대비해 0010일 경우 2로 보지 않고 2번째 자리에 1이 있어 $2^1$의 윗첨자만 가져와 1로 보았다.

그렇기 때문에 add 연산을 예로 add 2이고 bit가 0일 경우
bit |= (1 << 2 - 1)면 $bit=0010_two=2_ten$

하지만 위 코드는 0이 들어왔을 경우 1 << 0 - 1을 하는 상황을 방지하기 위해
bit |= (1 << 2)로 $bit=0100_two=4_ten$

and의 경우 or 연산을 해야 피연산자가 모두 bit에 1로 찍히기 때문에 or 연산을 했다.

remove연산의 경우 bit가 0110이고 remove 2라는 연산이 들어왔을 때 2 = 0100이므로 이 비트를 not한 1011과 and 연산을 해서 0010만 남기는 방식을 택했다.
즉, not과 and 연산을 이용했다.

check 연산의 경우 and 연산을 확인했는데 같지 않을 경우 집합에 해당 수가 없다는 의미가 되므로 결과값이 0일 땐 0을 버퍼에 입력했고, 0이 아닌 값이 나왔을 경우는 모두 1로 버퍼에 값을 입력했다.

toggle의 경우 집합에 해당 수가 있으면 삭제하고, 없으면 입력하는 것이므로 xor 연산을 택했다.
xor연산은 같을 경우 0으로 하고, 다를 경우 1로 하기 때문에 같을 경우(= 해당 수가 있을 경우) 0으로 바꿔 삭제를 하고, 다를 경우(= 해당 수가 없을 경우) 1 로 바꿔 입력을 해 주었다.

all 연산의 경우 모두 1로 바꿔주게 되는데 이 때 0을 not 연산한 비트와 or 연산을 하면 모두 1로 바꿀 수 있게 된다.

empty 연산의 경우 모두 0으로 바꿔줘야 하는데 0과 and 연산을 하면 모든 수를 0으로 바꿀 수 있다.