백준(BOJ) 11723 : 집합 (실버5) / 자바(Java) 풀이

문제

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

3줄 요약

1. 비트마스킹을 활용하여 집합의 상태를 저장할 변수 set을 초기화하고, 주어진 연산을 순차적으로 수행합니다.
2. 각 연산에서는 비트 연산자를 사용하여 집합의 상태를 변경하거나 확인합니다.
   • "add" 연산은 비트 OR 연산(|=)을 통해 해당 비트를 1로 설정하여 원소를 추가합니다.
   • "check" 연산은 비트 AND 연산(&)을 통해 해당 비트가 1인지 확인하여 원소의 존재 여부를 판단합니다.
   • "remove" 연산은 비트 AND 연산(&=)과 비트 NOT 연산(~)을 통해 해당 비트를 0으로 설정하여 원소를 제거합니다.
   • "toggle" 연산은 비트 XOR 연산(^=)을 통해 해당 비트를 반전시켜 원소의 존재 여부를 토글합니다.
3. 비트마스킹을 활용한 집합 연산을 통해 메모리 사용량을 줄이고 빠른 연산 속도를 얻을 수 있습니다.

코드

// package boj11723;

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력 파일에서 데이터 읽기 (테스트용)
        // System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 수행해야 하는 연산의 수 M 입력받기
        int M = Integer.parseInt(br.readLine());
        
        // 비트마스킹을 활용한 집합 상태 저장 변수
        int set = 0;
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // M개의 연산 수행
        for (int i = 0; i < M; i++) {
            String[] tmp = br.readLine().split(" ");
            String cmd = tmp[0];
            int val;
            
            switch (cmd) {
                case "all":
                    // 집합을 {1, 2, ..., 20}으로 변경
                    set = (1 << 21) - 1;
                    break;
                case "empty":
                    // 집합을 공집합으로 변경
                    set = 0;
                    break;
                case "add":
                    // 집합에 x를 추가
                    set |= 1 << Integer.parseInt(tmp[1]);
                    break;
                case "check":
                    // 집합에 x가 있는지 확인하여 결과 출력
                    val = 1 << Integer.parseInt(tmp[1]);
                    if ((set & val) != 0) {
                        bw.write("1\n");
                    } else {
                        bw.write("0\n");
                    }
                    break;
                case "remove":
                    // 집합에서 x를 제거
                    val = 1 << Integer.parseInt(tmp[1]);
                    set &= ~val;
                    break;
                case "toggle":
                    // 집합에서 x가 있으면 제거, 없으면 추가
                    set ^= 1 << Integer.parseInt(tmp[1]);
                default:
                    break;
            }
        }
        
        br.close();
        bw.flush();
        bw.close();
    }
}