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 연산이 주어질 때마다, 결과를 한 줄에 하나씩 출력합니다.

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

풀이 1: HashSet을 활용한 시뮬레이션

가장 직관적으로 집합 연산을 구현하는 방법은 자바의 HashSet 자료구조를 사용하는 것입니다.

1. 상태 관리: HashSet<Integer> set을 선언하여 집합의 상태를 관리합니다.
2. 연산 분기: 입력된 명령어(add, remove, check, toggle, all, empty)에 따라 분기 처리를 합니다.
   • all 연산은 1부터 20까지 반복문을 돌며 값을 집어넣습니다.
   • empty 연산은 새로운 빈 HashSet 객체를 생성하여 초기화합니다.
   • 나머지 연산들은 contains, add, remove 등의 내장 메서드를 적절히 활용하여 구현합니다.

이 방식은 코드가 직관적이고 이해하기 쉽지만, 연산의 수가 최대 300만 개인 이 문제에서는 해시 충돌이나 객체 생성 등으로 인한 오버헤드가 발생하여 실행 속도가 다소 느려질 수 있습니다.

코드 1

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

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());
       Set<Integer> set = new HashSet<>();

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

          if (s.equals("all")) {
             for (int i = 1; i <= 20; i++) {
                set.add(i);
             }
          } else if (s.equals("empty")) {
             set = new HashSet<>();
          } else {
             int x = Integer.parseInt(st.nextToken());
             if (s.equals("add")) {
                set.add(x);
             } else if (s.equals("remove")) {
                set.remove(x);
             } else if (s.equals("check")) {
                bw.write(set.contains(x) ? "1\n" : "0\n");
             } else if (s.equals("toggle")) {
                if (set.contains(x)) {
                   set.remove(x);
                } else {
                   set.add(x);
                }
             }
          }
       }

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

풀이 2: 비트마스킹

집합에 포함될 수 있는 원소의 범위가 1부터 20까지로 매우 작습니다. 이럴 때는 정수 자료형(int) 하나를 사용하여 0번부터 20번까지의 비트를 켜고 끄는 비트마스킹(Bitmasking) 방식을 사용하면, 메모리 사용량을 획기적으로 줄이고 연산 속도를 비약적으로 높일 수 있습니다.

1. 상태 변수: 정수형 변수 s를 0으로 초기화합니다. x가 집합에 있다면 s의 x번째 비트가 1이 되고, 없다면 0이 됩니다.
2. 비트 연산 적용:
   • add x: s |= (1 << x)를 통해 x번째 비트를 1로 켭니다. (OR 연산)
   • remove x: s &= ~(1 << x)를 통해 x번째 비트를 0으로 끕니다. (NOT 후 AND 연산)
   • check x: (s & (1 << x)) != 0을 통해 x번째 비트가 1인지 확인합니다. (AND 연산)
   • toggle x: s ^= (1 << x)를 통해 x번째 비트를 반전시킵니다. (XOR 연산)
   • all: s = (1 << 21) - 1을 통해 0번부터 20번까지의 비트를 모두 1로 채웁니다.
   • empty: s = 0을 통해 모든 비트를 0으로 초기화합니다.

코드 2

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

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 s = 0; // 비트마스킹을 위한 상태 변수

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

          if (op.equals("all")) {
             // 0부터 20까지의 비트를 모두 1로 설정
             s = (1 << 21) - 1; 
          } else if (op.equals("empty")) {
             // 공집합
             s = 0; 
          } else {
             int x = Integer.parseInt(st.nextToken());
             
             if (op.equals("add")) {
                // x번째 비트 켜기
                s |= (1 << x);
             } else if (op.equals("remove")) {
                // x번째 비트 끄기
                s &= ~(1 << x);
             } else if (op.equals("check")) {
                // x번째 비트 확인
                bw.write((s & (1 << x)) != 0 ? "1\n" : "0\n");
             } else if (op.equals("toggle")) {
                // x번째 비트 반전
                s ^= (1 << x);
             }
          }
       }

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

알고리즘 분류

구현, 비트마스킹 (Bitmasking)