문제

풀이

이해

자료구조 집합에 대해서 각각의 연산을 수행하면 된다. 연산은 add, remove, check, toggle, all, empty 6가지로 문제에 나와있듯이 간단하게 처리하면 된다.

접근

최초에 집합을 나타낼 자료구조로 boolean형 배열을 선택하였다. 배열은 0부터 20까지의 공간을 가지며 공간 내에 숫자가 add 되면 해당 숫자의 인덱스로 공간을 true로 초기화하였다. 반대로 remove의 경우에는 false로 초기화하였다.

check의 경우에는 해당 인덱스에 바로 접근해서 판단하였고 toggle은 람다식을 통해 값을 전환하였다.

all과 empty는 Arrays.fill() 메서드를 통해서 초기화시켜주었다.

하지만 배열형으로 풀었을 때 시간초과가 발생하였다.

시간초과가 발생한 연산을 생각해보았을 때 all과 empty에서 발생한 듯 보였다. all과 empty는 Arrays.fill()을 활용하는데 해당 메서드의 시간복잡도가 O(N)이기 때문이다.

따라서, 다른 방법을 찾아보다가 비스마스크를 활용한 풀이방법을 찾게 되었다.
참고 블로그

비트 마스크를 사용하면 모든 연산의 시간복잡도가 O(1)이 되기 때문에 시간초과를 해결할 수 있다.

코드

package java_baekjoon;

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

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

        int bit_set = 0;

        int M = Integer.parseInt(br.readLine());

        while(M --> 0){
            StringTokenizer st =new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            int num;
            switch(cmd){
                case "add":
                    num = Integer.parseInt(st.nextToken());
                    bit_set |= (1 << (num -1));
                    break;
                case "remove":
                    num = Integer.parseInt(st.nextToken());
                    bit_set = bit_set & ~(1<<(num-1));
                    break;
                case "check":
                    num = Integer.parseInt(st.nextToken());
                    sb.append((bit_set & (1 << (num - 1))) != 0 ? "1\n" : "0\n");
                    break;
                case "toggle":
                    num = Integer.parseInt(st.nextToken());
                    bit_set ^= (1 << (num-1));
                    break;
                case "all":
                    bit_set |= (~0);
                    break;
                case "empty":
                    bit_set &= 0;
                    break;
            }
        }
        System.out.println(sb.toString());
        return;
    }
}

코드는 참고 사이트의 코드와 거의 동일하다. 비트 마스크에 대한 내용은 추후에 정리할 예정이다.

결과