[Java] Baekjoon Online Judge 11723: 집합

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

 

⏳메모리 제한

---

• Java 8: 448 MB
• Java 8 (OpenJDK): 448 MB
• Java 11: 448 MB
• Kotlin (JVM): 448 MB
• C#: 64 MB
• Java 15: 448 MB
• F#: 64 MB
• Visual Basic: 64 MB

 

예제입력 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

 

🔎알고리즘 분류

---

• 구현
• 비트마스킹

 

📌풀이

---

코드 1

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int m = Integer.parseInt(br.readLine()); // 연산의 수
        boolean[] set = new boolean[21]; // 집합을 나타내는 배열 (인덱스 1부터 사용)

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            String[] operation = br.readLine().split(" ");

            switch (operation[0]) {
                case "add":
                    add(set, Integer.parseInt(operation[1]));
                    break;
                case "remove":
                    remove(set, Integer.parseInt(operation[1]));
                    break;
                case "check":
                    sb.append(check(set, Integer.parseInt(operation[1]))).append('\n');
                    break;
                case "toggle":
                    toggle(set, Integer.parseInt(operation[1]));
                    break;
                case "all":
                    all(set);
                    break;
                case "empty":
                    empty(set);
                    break;
            }
        }

        System.out.println(sb);
    }

    static void add(boolean[] set, int x) {
        set[x] = true;
    }

    static void remove(boolean[] set, int x) {
        set[x] = false;
    }

    static int check(boolean[] set, int x) {
        return set[x] ? 1 : 0;
    }

    static void toggle(boolean[] set, int x) {
        set[x] = !set[x];
    }

    static void all(boolean[] set) {
        for (int i = 1; i <= 20; i++) {
            set[i] = true;
        }
    }

    static void empty(boolean[] set) {
        for (int i = 1; i <= 20; i++) {
            set[i] = false;
        }
    }
}

 

코드 2

import java.io.DataInputStream;
import java.io.IOException;

public class Main {
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            return neg ? -ret : ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din != null)
                din.close();
        }
    }

    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        StringBuilder out = new StringBuilder();

        int M = in.nextInt();
        int bit = 0, cnt = 0;

        while (M-- > 0) {
            char operation = (char) in.read();
            switch (operation) {
                case 'a':
                    if (in.read() == 'd') {
                        in.read();
                        bit |= 1 << in.nextInt() - 1;
                    } else {
                        in.read(); in.read();
                        bit = (1 << 20) - 1;
                    }
                    break;
                case 'r':
                    in.read(); in.read(); in.read(); in.read(); in.read();
                    bit &= ~(1 << in.nextInt() - 1);
                    break;
                case 'c':
                    in.read(); in.read(); in.read(); in.read();
                    out.append((bit & 1 << in.nextInt() - 1) != 0 ? 1 : 0).append('\n');
                    if (++cnt == 100000) {
                        cnt = 0;
                        System.out.print(out);
                        out.setLength(0);
                    }
                    break;
                case 't':
                    in.read(); in.read(); in.read(); in.read(); in.read();
                    bit ^= 1 << in.nextInt() - 1;
                    break;
                default:
                    in.read(); in.read(); in.read(); in.read(); in.read();
                    bit = 0;
                    break;
            }
        }

        System.out.print(out);
        in.close();
    }
}

 

 

코드 3

import java.io.DataInputStream;
import java.io.IOException;

public class Main {
    // 입력을 빠르게 받기 위한 Reader 클래스
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            // 생성자에서 필요한 초기화 작업
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        // 다음 정수를 읽어오는 메서드
        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            // 공백 문자 무시
            while (c <= ' ') {
                c = read();
            }
            // 음수 여부 확인
            boolean neg = (c == '-');
            if (neg)
                c = read();
            // 숫자로 변환
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            // 음수인 경우 처리
            return neg ? -ret : ret;
        }

        // 버퍼를 채우는 메서드
        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        // 버퍼에서 한 바이트씩 읽어오는 메서드
        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        // 스트림을 닫는 메서드
        public void close() throws IOException {
            if (din != null)
                din.close();
        }
    }

    public static void main(String[] args) throws IOException {
        // Reader 객체 생성
        Reader in = new Reader();
        // 출력 결과를 저장하기 위한 StringBuilder 객체 생성
        StringBuilder out = new StringBuilder();

        // 연산의 수를 입력 받음
        int M = in.nextInt();
        // 비트 연산에 사용할 변수 초기화
        int bit = 0;
        // 출력 횟수를 관리하는 변수 초기화
        int cnt = 0;

        // 연산의 수만큼 반복
        while (M-- > 0) {
            // 다음 연산의 종류를 문자로 읽어옴
            char operation = (char) in.read();
            // 각 연산 종류에 따라 처리
            switch (operation) {
                case 'a': // add 또는 all 연산
                    if (in.read() == 'd') { // add 연산
                        in.read(); // 공백 문자 무시
                        // 해당 비트를 1로 설정
                        bit |= 1 << in.nextInt() - 1;
                    } else { // all 연산
                        in.read(); in.read(); // 두 개의 문자를 무시하여 'll'을 처리
                        // 모든 비트를 1로 설정
                        bit = (1 << 20) - 1;
                    }
                    break;
                case 'r': // remove 연산
                    in.read(); in.read(); in.read(); in.read(); in.read(); // 다섯 개의 문자를 무시하여 'emove'를 처리
                    // 해당 비트를 0으로 설정
                    bit &= ~(1 << in.nextInt() - 1);
                    break;
                case 'c': // check 연산
                    in.read(); in.read(); in.read(); in.read(); // 네 개의 문자를 무시하여 'heck'를 처리
                    // 해당 비트가 1이면 1, 아니면 0을 출력
                    out.append((bit & 1 << in.nextInt() - 1) != 0 ? 1 : 0).append('\n');
                    // 출력이 100,000번마다 출력 버퍼를 비우기
                    if (++cnt == 100000) {
                        cnt = 0;
                        System.out.print(out);
                        // StringBuilder 초기화
                        out.setLength(0);
                    }
                    break;
                case 't': // toggle 연산
                    in.read(); in.read(); in.read(); in.read(); in.read(); // 다섯 개의 문자를 무시하여 'oggle'을 처리
                    // 해당 비트가 1이면 0으로, 0이면 1로 변경
                    bit ^= 1 << in.nextInt() - 1;
                    break;
                default: // empty 연산
                    in.read(); in.read(); in.read(); in.read(); in.read(); // 다섯 개의 문자를 무시하여 'mpty'를 처리
                    // 모든 비트를 0으로 설정
                    bit = 0;
                    break;
            }
        }

        // 출력 결과를 출력
        System.out.print(out);
        // Reader를 닫음
        in.close();
    }
}