[JAVA] 백준 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를 공집합으로 바꾼다.

풀이

비트마스킹 문제를 해결하기 위한 비트를 이용한 집합 연산을 계산하는 기본 문제였다.

• add : set |= (1 << k), k번 1을 왼쪽 shift하고 OR연산하면 바꾸려는 비트만 1로 교체할 수 있다.
  • set = 1 1 0 1 1 0 0, k = 1
  • 계산 : 1 1 0 1 1 0 0 OR 0 0 0 0 0 1 0 = 1 1 0 1 1 1 0
• remove : set &= ~(1 << k), k번 1을 왼쪽 shift하고 NOT연산 후 AND연산 하면 바꾸려는 비트만 0으로 교체할 수 있다.
  • set = 1 1 0 1 1 0 0, k = 3
  • 계산 : 1 1 0 1 1 0 0 AND NOT(0 0 0 1 0 0 0) = 1 1 0 1 1 0 0 AND 1 1 1 0 1 1 1 = 1 1 0 0 1 0 0
• check : (set & (1 << k)) == (1 << k)가 true라면 1 아니라면 0이 된다.
  • set = 1 1 0 1 1 0 0 , 2번 비트 위치를 체크하고 싶다. k = 2
  • 계산 : (1 1 0 1 1 0 0 AND (0 0 0 0 1 0 0)) = 0 0 0 0 1 0 0 == 0 0 0 0 1 0 0 = true
  • 2번 비트 위치는 1로 세트되어 있다.
• toggle : set ^= (1 << k), k위치를 XOR연산을 통해 0이면 1, 1이면 0으로 바꾼다.
  • set = 1 1 0 1 1 0 0, 4번 위치를 바꾸고 싶다. k = 4
  • 계산 : 1 1 0 1 1 0 0 XOR 0 0 1 0 0 0 0 = 1 1 1 1 1 0 0
• all : set = (1 << k) - 1 (k는 집합으로 사용하는 비트의 최대 값 + 1이다.)
  • set = 1 1 0 1 1 0 0, 크기는 6이다.
  • 계산 : 1 0 0 0 0 0 0 0 (1 << 7) - 1 = 0 1 1 1 1 1 1
• empty : set = 0, 공집합으로 만든다.

📌 전체 코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());

        int set = 0;
        for(int i=0; i<N; i++){
            String[] value = br.readLine().split(" ");

            String operation = value[0];

            switch (operation){
                case "add":
                    int num = Integer.parseInt(value[1]);
                    set |= (1 << num);
                    break;
                case "remove":
                    num = Integer.parseInt(value[1]);
                    set &= ~(1 << num);
                    break;
                case "check":
                    num = Integer.parseInt(value[1]);
                    sb.append( ((set & (1 << num) )== (1 << num)) ? 1 : 0).append("\n");
                    break;
                case "toggle":
                    num = Integer.parseInt(value[1]);
                    set ^= (1 << num);
                    break;
                case "all":
                    set = (1 << 21) - 1;
                    break;
                case "empty":
                    set = 0;
                    break;
            }
        }
        System.out.println(sb);
    }

}

결과