11723번: 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하는 문제입니다. 숫자 $x$의 범위는 1부터 20까지로 매우 작습니다.

• add x: S에 $x$를 추가합니다. (이미 있는 경우 무시)
• remove x: S에서 $x$를 제거합니다. (없는 경우 무시)
• check x: S에 $x$가 있으면 1을, 없으면 0을 출력합니다.
• toggle x: S에 $x$가 있으면 제거하고, 없으면 추가합니다.
• all: S를 {1, 2, ..., 20}으로 바꿉니다.
• empty: S를 공집합으로 바꿉니다.
• 입력: 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)
• 출력: check 연산이 주어질 때마다 결과를 출력합니다.

풀이: 비트마스킹을 활용한 메모리 최적화

이 문제의 핵심은 4MB라는 극도로 적은 메모리 제한과 300만 번의 많은 연산 횟수입니다. 일반적인 HashSet<Integer>나 boolean[] 배열을 사용할 경우 자바의 객체 오버헤드나 배열 메모리로 인해 메모리 초과(MLE)가 발생할 가능성이 매우 높습니다.

비트 연산 적용 원리

자바의 int형은 32비트(4바이트) 정수입니다. 문제에서 다루는 숫자가 1부터 20까지이므로, 각 비트의 자릿수를 숫자의 존재 여부(0 또는 1)로 매핑하여 단 하나의 변수로 집합을 표현할 수 있습니다.

• add x (mask |= 1 << x): OR 연산을 사용하여 $x$번째 비트를 1로 만듭니다.
• remove x (mask &= ~(1 << x)): NOT 연산으로 $x$번째 비트만 0으로 만든 마스크를 생성한 뒤, AND 연산으로 해당 비트를 끕니다.
• check x ((mask & (1 << x)) != 0): AND 연산을 통해 $x$번째 비트가 켜져 있는지 확인합니다.
• toggle x (mask ^= (1 << x)): XOR 연산을 사용하여 비트가 1이면 0으로, 0이면 1로 반전시킵니다.
• all (mask = (1 << 21) - 1): 1부터 20까지 모든 비트를 1로 채웁니다.
• empty (mask = 0): 모든 비트를 0으로 초기화합니다.

코드

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

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 m = Integer.parseInt(br.readLine());
       int mask = 0; // 집합 상태를 관리할 비트마스크 변수 (단 4바이트)

       while (m-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          String cmd = st.nextToken();
          int x;

          switch (cmd) {
             case "add":
                x = Integer.parseInt(st.nextToken());
                mask |= 1 << x;
                break;
             case "remove":
                x = Integer.parseInt(st.nextToken());
                mask &= ~(1 << x);
                break;
             case "check":
                x = Integer.parseInt(st.nextToken());
                // x번째 비트가 켜져 있다면 1, 아니라면 0 출력
                bw.write((mask & (1 << x)) != 0 ? "1\\n" : "0\\n");
                break;
             case "toggle":
                x = Integer.parseInt(st.nextToken());
                mask ^= (1 << x);
                break;
             case "all":
                // 21번째 비트 미만을 모두 1로 채움
                mask = (1 << 21) - 1;
                break;
             case "empty":
                mask = 0;
                break;
          }
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

구현 (Implementation), 비트마스킹 (Bitmasking)