[Baekjoon] 11723 집합 - JAVA

문제

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

예제 입력 1

26
add 1
add 2
check 1
check 2
check 3
remove 2
check 1
check 2
toggle 3
check 1
check 2
check 3
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1

예제 출력 1 

1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0

 

---

📝 제출 답안

❌ 오답 - HashSet 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static HashSet<Integer> set = new HashSet<>();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            operation(str);
        }
    }

    public static void operation(String str) {
        if (str.equals("all") || str.equals("empty")) {
            switch (str) {
                case "all":
                    set.clear();
                    for (int i = 1; i <= 20; i++) {
                        set.add(i);
                    }
                    break;
                case "empty": set.clear(); break;
            }
        } else {
            int x = Integer.parseInt(st.nextToken());
            switch (str) {
                case "add": set.add(x); break;
                case "remove": set.remove(x); break;
                case "check":
                    int res = set.contains(x) ? 1 : 0;
                    System.out.println(res);
                    break;
                case "toggle":
                    if(set.contains(x)) set.remove(x);
                    else set.add(x);
                    break;
            }
        }
    }
}

 

⭕ 정답 - 비트마스크 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int s;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            operation(str);
        }
        System.out.println(sb);
    }

    public static void operation(String str) {
        if (str.equals("all") || str.equals("empty")) {
            switch (str) {
                case "all": s = (1 << 21) - 1; break;
                case "empty": s = 0; break;
            }
        } else {
            int x = Integer.parseInt(st.nextToken());
            switch (str) {
                case "add": s |= (1<<x); break;
                case "remove": s &= ~(1<<x); break;
                case "check": sb.append((s & (1 << x)) != 0 ? 1 : 0).append("\n"); break;
                case "toggle": s ^= (1<<x); break;
            }
        }
    }
}

 

제목부터 집합이어서 당연하게 HashSet을 사용해서 풀었지만 시간 초과가 떴다.

구글링을 해보고 힌트를 열어 본 결과 비트마스크를 사용해 푸는 문제였다.

처음 들어본 자료구조라서 비트마스크로 접근할 생각도 못했다.

자료구조 관련 공부를 더 많이 해야겠다는 생각을 하게 됐다.

---

 🪄비트마스크?

: 비트마스크는 이진수와 각 비트를 사용해 집합이나 플래그의 상태를 나타내는 기법이다. 메모리를 절약하고 연산 속도를 빠르게 할 수 있다.

 

비트 연산

1. 추가 add x

• 연산 : s |= (1 << x)
• 설명 : x 번째 비트를 1로 설정하여 or 연산을 통해 숫자 x를 추가한다.
• 예시 : s = 0101 에서 add 2 를 하면 s = 0111

2. 제거 remove x

• 연산 : s &= ~(1 << x)
• 설명 : x 번째 비트를 0으로 설정하여 and 연산을 통해 숫자 x를 제거한다.
• 예시 : s = 0111 에서 remove 2를 하면 s = 0101

3. 확인 check x

• 연산 : (s & (1 << x)) != 0
• 설명 : x 번째 비트가 1인지 확인하여 숫자 x를 포함하는지 확인한다.
• 예시 : s = 0101 에서 check 2를 하면 true. (2번째 비트가 1이므로)

4. 반전 toggle x

• 연산 : s ^= (1 << x)
• 설명 : x 번째 비트를 xor 연산으로 반전시킨다. (1↔0)
• 예시 : s = 0101 에서 toggle 2를 하면 s = 0111

5. 초기화 empty

• 연산 : s = 0
• 설명 : 모든 비트를 0으로 설정하여 집합을 초기화한다.
• 예시 : s = 1111 에서 empty를 하면 s = 0000

---

코드를 최대한 효율적으로 작성하여 시간 초과를 줄이기 위해 BufferedReader와 StringTokenizer, StringBuilder를 사용해 입력과 출력을 처리해주었다.

 

정수형 변수 s를 사용하여 집합을 표현한다. s는 21비트 크기의 비트마스크로 각 비트가 특정 숫자의 존재 여부를 나타낸다. 예를 들어 s의 i번째 비트가 1이면 숫자 i가 집합에 포함되어 있는 것이다.

 

각 명령어에 따라 operation 메서드에서 명령을 수행하고, check 명령의 결과를 StringBuilder에 누적하여 마지막에 출력한다.

 

제출 현황