[BOJ] 11723 - 집합 JAVA

www.acmicpc.net/problem/11723

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

예제 입력 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

 

 

 

 

 

 

 

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        int S = 0;
        while(n-- > 0) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int num = 0;

            switch(str) {
                case "add" :
                    num = Integer.parseInt(st.nextToken()) - 1;
                    S = S | (1 << num);
                    break;
                case "remove" :
                    num = Integer.parseInt(st.nextToken()) - 1;
                    S = S & ~(1 << num);
                    break;
                case "check" :
                    num = Integer.parseInt(st.nextToken()) - 1;
                    int temp = S & (1 << num);
                    sb.append(((temp == 0) ? 0 : 1) + "\n");
                    break;
                case "toggle" :
                    num = Integer.parseInt(st.nextToken()) - 1 ;
                    S = S ^ (1 << num);
                    break;
                case "all" :
                    S = (1 << 21) - 1;
                    break;
                case "empty" :
                    S = 0;
                    break;
            }
        }
        System.out.println(sb.toString());
    }
}

 

기본적인 비트연산을 사용한 비트마스킹 문제.

 

예전에 비트마스킹을 공부할 기회가 있었으나 어려워보여서 외면하고 다른 쪽으로 넘어갔었다.

그렇게 다른 알고리즘만 공부하다가 비트마스킹의 효용성에 대해 알게 되어 지금이라도 익혀둬야겠다 싶었다.

 

하나의 정수를 이진수로 바꿨을 때, 특정 자리수의 비트가 1인지 0인지 판별하거나 특정 비트를 더하거나 빼거나 바꾸는 것을 비트연산을 통해 활 수 있다.

 

 

주의할 점,

20자리의 이진수가 있을 때, 각 비트의 자리수는 0~19이다.

문제에서는 1~20에 대한 입력으 받기 때문에 -1을 해주어 0~19로 맞춰줘야 한다.