[JAVA] 백준 (실버5) 11723번 집합

링크

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

---

문제 설명

정답률 29.558%

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

---

풀이

이 문제는 자바 컬렉션의 Set을 이용하거나 비트마스크를 이용해서 풀 수 있다.

HashSet을 이용해 푼 코드는 단순히 각 경우에 대해서 원소를 넣고 빼고만 해주면 되니 간단하다.

HashSet 코드

public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        HashSet<String> set = new HashSet<>();
        
        for (int i = 0; i < M; i++) {
            String[] split = br.readLine().split(" ");
            String operation = split[0];

            switch (operation) {
                case "add" -> set.add(split[1]);
                case "remove" -> set.remove(split[1]);
                case "check" -> {
                    if (set.contains(split[1])) {
                        sb.append(1).append("\n");
                    } else {
                        sb.append(0).append("\n");
                    }
                }
                case "toggle" -> {
                    if (set.contains(split[1])) {
                        set.remove(split[1]);
                    } else {
                        set.add(split[1]);
                    }
                }
                case "all" -> {
                    for (int j = 1; j <= 20; j++) {
                        set.add(String.valueOf(j));
                    }
                } default -> set.clear();
            }
        }

        System.out.println(sb);
    }
}

HashSet은 내부적으로 해시 테이블을 사용하여 원소를 저장하는데 요소 추가, 삭제, 검색의 시간 복잡도는 평균적으로 $O(1)$이지만 해시 테이블을 유지하기 위한 추가적인 메모리 오버헤드가 있으며, 요소 수가 많아질수록 해시 충돌을 방지하기 위한 메모리 사용량이 증가 할 수 있다.

하지만 비트마스크는 기본적으로 정수 하나를 이용하여 집합을 표현하므로 메모리 접근이 매우 빠르다. 문제에서는 M이 최댓값이 3,000,000이므로 이러한 작은 차이가 누적되면 꽤 큰 차이가 발생할 수 있다.

그래서 비트마스크를 이용한 풀이를 보면 우선 20개의 요소를 포함하는 집합은 20비트 크기의 정수 하나로 표현할 수 있다. 그리고 각 연산은 다음과 같이 나타낸다. S는 6자리 비트라 가정한다.

• add: S |= (1 << x)
  • 1 << 3은 001000
  • S = 000000, x = 3일 때 위 연산은 S = 001000이 된다.
• remove: S &= ~(1 << x)
  • ~(1 << 3)은 110111
  • S = 111111, x = 3일 때 위 연산은 S = 110111이 된다.
• check: S & (1 << x)
  • S & (1 << x)은 x번째 비트가 1인지 확인한다.
• toggle: S ^= (1 << x)
  • S ^= (1 << x)은 x번째 비트를 반전시킨다.
  • ^는 XOR 연산이고 0 ^ 1 = 1, 1 ^ 1 = 0 이므로 x번째 비트를 반전시킨다.
• all: S = (1 << 21) - 1
  • 1 << 21은 $2^{21}$, 100...000을 의미하고 여기서 1을 빼면 S = 111111111111111111111이고 이는 집합 {1, 2, ..., 20}을 의미한다.

비트마스크 코드

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

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int S = 0;  //비트 마스크 초기화

        for (int i = 0; i < M; i++) {
            String[] split = br.readLine().split(" ");
            String operation = split[0];
            int x = 0;
            if (split.length == 2) {
                x = Integer.parseInt(split[1]);
            }

            switch (operation) {
                case "add" -> S |= (1 << x);
                case "remove" -> S &= ~(1 << x);
                case "check" -> {
                    int target = S & (1 << x);
                    if (target != 0) {
                        sb.append(1).append("\n");
                    } else {
                        sb.append(0).append("\n");
                    }
                }
                case "toggle" -> S ^= (1 << x);
                case "all" -> S = (1 << 21) - 1;
                default -> S = 0;
            }
        }

        System.out.println(sb);
    }
}