[JAVA] 백준 11723번- 집합(비트 마스크)

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

11723번: 집합

 

 

 

Set 사용

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

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

        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        int bitset = 0;

        Set<Integer> set = new HashSet<>();

        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int x;

            switch (str) {
                case "add":
                    x = Integer.parseInt(st.nextToken());
                    set.add(x);
                    break;
                case "check":
                    x = Integer.parseInt(st.nextToken());
                    if (set.contains(x)) sb.append(1+"\n");
                    else sb.append(0+"\n");
                    break;
                case "remove":
                    x = Integer.parseInt(st.nextToken());
                    set.remove(x);
                    break;
                case "toggle":
                    x = Integer.parseInt(st.nextToken());
                    if (set.contains(x)) set.remove(x);
                    else set.add(x);
                    break;
                case "all":
                    for (int j = 1; j <= 20; j++) set.add(j);
                    break;
                case "empty":
                    set.clear();
                    break;

            }
        }
        System.out.println(sb);
    }

}

 

set으로 풀었을 때, println으로 하면 시간초과가 났고 StringBuilder를 사용하니 통과됐다. 

 

 

 

비트 마스크 사용

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

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

        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        int bitset = 0;

        while (m-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            int x;
            int k = 1<<x-1;

            switch (str) {
                case "add":
                    x = Integer.parseInt(st.nextToken());
                    bitset = bitset | k; 
                    break;
                case "remove":
                    x = Integer.parseInt(st.nextToken());
                   bitset = bitset & ~k;
                    break;
                case "check":
                    x = Integer.parseInt(st.nextToken());
                   if((bitset & k) != 0) sb.append("1\n");
                   else sb.append("0\n");
                    break;
                case "toggle":
                    x = Integer.parseInt(st.nextToken());
                    bitset = bitset ^ k;
                    break;
                case "all":
                    bitset = bitset | (~0);
                    break;
                case "empty":
                    bitset = bitset & 0;
                    break;

            }
        }
        System.out.println(sb);
    }

}

 

 

비트 마스킹을 잘 몰라서 참고해 풀었다. 

정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 

비트 마스크를 사용하면 수행 시간이 더 빠르고 메모리 사용을 적게 한다. 

 

우선 k변수에 1<<(x-1) 을 저장한다. k는 x-1번의 비트가 1인 값이다. 

 

add

bitset = bitset | k; 

a|b 연산은 a,b 하나라도 1이면 결과는 1이다. 

bitset의 k위치의 비트가 원래 0이든 1이든 1로 만들게 된다. 

 

 

remove

bitset = bitset & ~k;

a&b 연산은 a,b 둘다 1이여야 결과가 1이 된다.

~ 연산을 통해 k위치의 비트만 0, 나머지 비트는 1로 만든다.

그리고 & 연산을 하면 k위치의 비트가 0이 된다.

 

toggle

bitset = bitset ^ k;

^는 서로 다르면 1, 같으면 0이다. 따라서 1이면 0으로 바뀌고 0이면 1로 바뀐다. 

 

check

(bitset & k) != 0

& 연산을 통해 둘 다 1이라 결과가 1이 나오면 k위치의 비트가 1인 것이므로 1을 출력하고 아니면 0을 출력한다.

 

all

bitset = bitset | (~0);

1과 | 연산을 해 모든 값을 1로 바꾼다.   

 

empty

bitset = bitset & 0;

0과 &연산을해 모든 값을 0으로 바꾼다. 

 

 

 

 

참고

https://travelbeeee.tistory.com/451