[Baekjoon] 11723번: 집합 - Java

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

11723번: 집합

문제 설명

집합 개념에 대한 간단한 문제이다. 다만 주의할 것은 시간과 메모리 제한이 있으므로 배열 또는 비트 연산자로 문제를 해결해야 한다.

풀이 방법 1. 배열

먼저 배열로 푸는 방법이 있다. 배열에 담기는 숫자가 20까지로 제한되어 있으므로 짧은 배열로 해결이 가능하다. 배열의 타입으로는 boolean과 int 타입을 둘 다 사용할 수 있지만 크기가 작은 boolean을 사용하면 된다.

코드

package baekjoon.impl;

import java.io.*;

public class BOJ11723 {
    private static final StringBuilder sb = new StringBuilder();
    private static final boolean[] set = new boolean[21];

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int M = Integer.parseInt(br.readLine());

            for (int i = 0; i < M; i++) {
                String input = br.readLine();
                String[] tokens = input.split(" ");

                String command = tokens[0];
                int num = 0;

                switch (command) {
                    case "add":
                        num = Integer.parseInt(tokens[1]);
                        set[num] = true;
                        break;
                    case "remove":
                        num = Integer.parseInt(tokens[1]);
                        set[num] = false;
                        break;
                    case "check":
                        num = Integer.parseInt(tokens[1]);
                        sb.append(set[num] == true ? "1\n" : "0\n");
                        break;
                    case "toggle":
                        num = Integer.parseInt(tokens[1]);
                        if (set[num] == true) {
                            set[num] = false;
                        } else {
                            set[num] = true;
                        }
                        break;
                    case "all":
                        for (int j = 1; j < set.length; j++) {
                            set[j] = true;
                        }
                        break;
                    case "empty":
                        for (int j = 1; j < set.length; j++) {
                            set[j] = false;
                        }
                        break;
                }
            }
            bw.write(sb.toString());
        }
    }
}

풀이 방법 2: 비트 연산

두 번째로 비트 연산을 활용한 방법이 있다. boolean이 true와 false를 이용한 것처럼 int형 변수 하나를 선언하고 32비트만큼을 0과 1로 사용할 수 있다. 알고리즘 분류에 비트마스킹으로 되어 있는 만큼 한 번 시도해 보는 것도 좋다.

package baekjoon.impl;

import java.io.*;

public class BOJ11723 {
    private static final StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int M = Integer.parseInt(br.readLine());
            int bitset = 0;

            for (int i = 0; i < M; i++) {
                String input = br.readLine();
                String[] tokens = input.split(" ");

                String command = tokens[0];
                int num = 0;

                switch (command) {
                    case "add":
                        num = Integer.parseInt(tokens[1]);
                        bitset |= (1 << (num - 1));
                        break;
                    case "remove":
                        num = Integer.parseInt(tokens[1]);
                        bitset &= ~(1 << (num - 1));
                        break;
                    case "check":
                        num = Integer.parseInt(tokens[1]);
                        sb.append((bitset & (1 << (num - 1))) != 0 ? "1\n" : "0\n");
                        break;
                    case "toggle":
                        num = Integer.parseInt(tokens[1]);
                        bitset ^= (1 << (num - 1));
                        break;
                    case "all":
                        bitset |= (~0);
                        break;
                    case "empty":
                        bitset &= 0;
                        break;
                }
            }
            bw.write(sb.toString());
        }
    }
}