이것저것 개발 블로그

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

풀이)

- 풀이1 -

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

public class Main_BJ_11723_집합 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        StringTokenizer st;
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            if(command.equals("all")){
                for(int j=0; j<21; j++){
                    map.put(j, 1);
                }
            }else if(command.equals("empty")){
                map.clear();
            }else{
                int num = Integer.parseInt(st.nextToken());
                switch (command){
                    case "add":
                        if(!map.containsKey(num))
                            map.put(num, 1);
                        break;
                    case "remove":
                        map.remove(num);
                        break;
                    case "check":
                        if(map.containsKey(num))
                            sb.append("1\n");
                        else
                            sb.append("0\n");
                        break;
                    case "toggle":
                        if(map.containsKey(num))
                            map.remove(num);
                        else
                            map.put(num, 1);
                        break;
                }//switch
            }
        }//for
        System.out.println(sb);
    }//main
}

만약, StringBuilder를 사용하지 않고, System.out.println을 사용한다면 시간초과를 볼 것이다!!

하지만 문제 자체가 비트마스크이므로, 한 번 찾아보았다.

- 비트마스킹을 활용한 풀이 -

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

public class Main_BJ_11723_집합2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        int bit = 0;
        StringTokenizer st;

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            String command = st.nextToken();
            int num;
            switch (command){
                case "add":
                    num = Integer.parseInt(st.nextToken());
                    //num-1 => 최대 20이기 때문에 0~19까지 자리수로 표현하기 때문.
                    bit |= (1 << (num-1));
                    break;
                case "remove":
                    num = Integer.parseInt(st.nextToken());
                    bit  &= ~(1 << (num-1));
                    break;
                case "check":
                    num = Integer.parseInt(st.nextToken());
                    sb.append((bit & (1<<(num-1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle":
                    num = Integer.parseInt(st.nextToken());
                    bit ^= (1 << (num-1));
                    break;
                case "all":
                    // bit |= (~0);
                    //21을 shift한 후 1을 빼면 모두 1~20까지 shift한 효과가 있다
                    bit = (1 << 21) - 1;
                    break;
                case "empty":
                    bit &= 0;
                    break;
            }//switch
        }
        System.out.println(sb);
    }//main
}

<BitMasking 이론>

비트마스킹

정수를 이진수로 표현하기 위해 쓰는 기법

빠른 수행 시간, 간결한 코드, 더 적은 메모리 사용을 할 수 있다.

비트 연산자

1. &
   • AND 연산
2. |
   • OR 연산
3. ^
   • XOR 연산
4. ~
   • NOT 연산
5. <<
   • 왼쪽 shift 연산
   • a << b : a를 b만큼 왼쪽으로 시프트
   • 1 << 2 == 100(2) => 4
6. >>
   • 오른쪽 shift 연산
   • a >> b : a를 b만큼 오른쪽으로 시프트
   • 4 >> 2 == 1(2) => 1

비트마스킹을 이용하면 기깔나게 잘 풀리는 문제들이 몇몇 있었는데, 다시 기억해보는 계기가 되었다