[백준] CLASS3 11723 집합 - JAVA [자바]

안녕하세요. 이번에는 백준 11723 집합 문제를 풀어보려고 합니다.

 

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

11723번: 집합

---

Problem

비어있는 공집합 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를 공집합으로 바꾼다.

사진 1. 문제

---

Solution

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

public class Main {
    
    static ArrayList<Integer> list;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int M = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine(), " ");
            String input = st.nextToken();
            int x;
            
            switch(input) {
                case "add" :
                    x = Integer.parseInt(st.nextToken());
                    if(!list.contains(x)) {
                        list.add(x);    
                    }
                    
                    break;
                case "remove" :
                    x = Integer.parseInt(st.nextToken());
                    
                    if(list.contains(x)) {
                        int idx = list.indexOf(x);
                        list.remove(idx);
                    }
                    break;
                case "check" :
                    x = Integer.parseInt(st.nextToken());
                    
                    if(list.contains(x)) {
                        sb.append("1").append("\n");
                    } else {
                        sb.append("0").append("\n");
                    }
                    break;
                case "toggle" :
                    x = Integer.parseInt(st.nextToken());
                    
                    if(list.contains(x)) {
                        int idx = list.indexOf(x);
                        list.remove(idx);
                    } else {
                        list.add(x);
                    }                    
                    break;
                case "all" :
                    list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20));
                    break;
                case "empty" :
                    list = new ArrayList<>();
                    break;
            }
        }
        System.out.println(sb.toString());
    }
}

 이번 문제는 ArrayList의 기능으로 풀 수 있는 문제였다. 그런데 알고리즘 분류를 확인하던 중 비트마스킹으로 분류되어있는 것을 확인하고 비트마스킹으로 푼 문제를 한번 확인해 보았다. 

 

Add : x를 추가하는 문제로 1 << x 와 OR 연상을 활용

Remove : x를 제거하기 위해 1 << x를  ~(not) 연산을 사용해 비트를 뒤집어 AND 연산을 활용

Check : x의 체크 여부를 확인하기 위해 1 << x와 마스킹한 값을 AND연산하여 0이 아니라면 값이 존재한다는 뜻이므로 1을 출력

Toggle : x의 연산을 뒤집어야 하므로 1 << x와 XOR 연산을 활용

All : 모든 비트를 체크해야 하기 때문에 (1 << 21) - 1로 값 변경

Empty : 공집합으로 0으로 값을 변경 

 

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));
        int M = Integer.parseInt(br.readLine());
        
        int bit = 0;
        StringBuilder sb = new StringBuilder();
        while(M-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String input = st.nextToken();
            int num;

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

향후 비트 연산자에 대한 공부를 좀 더 해보도록 해봐야겠다.

---

Performance

1. ArrayList를 사용해서 풀이한 실행 결과

사진 2. 실행 결과

 

2. 비트마스킹을 사용해서 풀이한 실행 결과

사진 3. 실행 결과