문제

비어있는 공집합 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 연산이 주어질때마다, 결과를 출력한다.

예제 입력

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
0
1
0
1
0
1
0
1
1
0
0
0
1
0

내가 했던 풀이 방법

1. Hashset 이용 -> 실패 (당연하게 안 될거라고 생각했으나 혹시나 하고 해봤는데 역시나)
2. 20크기의 boolean 배열을 모두 false로 만들어놓은 후, true/false를 통해 현재 집합에 포함되어있는지를 체크한다. -> 실패 (시간초과) System.out.println()의 속도가 느리다고 한다.
3. 2번 방법에 BufferedWriter를 사용하여 출력 -> 성공

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    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());

        boolean[] isContain = new boolean[20];
        Arrays.fill(isContain, false);
        StringBuilder answer = new StringBuilder();

        int number = 0;
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            if (input.length != 1) {
                number = Integer.parseInt(input[1]);
            }
            switch (input[0]) {
                case "add":
                    isContain[number - 1] = true;
                    break;
                case "remove":
                    isContain[number - 1] = false;
                    break;
                case "check":
                    answer.append(isContain[number - 1] ? "1\n" : "0\n");
                    break;
                case "toggle":
                    isContain[number - 1] = !isContain[number - 1];
                    break;
                case "all":
                    Arrays.fill(isContain, true);
                    break;
                case "empty":
                    Arrays.fill(isContain, false);
                    break;
            }
        }
        bw.write(answer.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

회고

초반에 이 방법을 System.out.print로 구현하고 시간초과가 나왔을 때 도저히 모르겠어서 찾아본 결과 비트마스킹을 이용하여 문제를 풀이하더라. 이 문제를 보고 비트마스킹을 유추할 수 있을까? 음.. 일단 어려울 것 같아서 boolean 배열을 최대한 활용해보고자 했다. 거기서 알게된 해답은 System.out.print를 버려라. 원래 Scanner까지 사용하다가 속도가 느리다고 해서 BufferReader를 사용했는데, 도저히 BufferWriter가 손에 익지를 않아서 Reader만 사용했는데 이제 슬슬 Writer도 사용해줘야 하는 시기가 되었나보다....