[백준/Java] 11723 집합 (feat. 비트마스크)

문제

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

 

# 입력

첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

# 출력

check 연산이 주어질 때마다, 결과를 출력한다.

 

 

 

---

 

 

 

브루트 포스 학습 마지막 단계인 비트마스크 관련 문제이다 👽

비트(bit) 연산을 통해 부분 집합을 표현하는 방법을 말하며,

(보통 어떤 비트가 1이면 "켜져있다" 0이면 "꺼져있다" 고 한다)

수행 시간이 빠르고 코드가 짧고 메모리 사용량이 적다는 장점을 가진다.

 

비트마스크를 사용하기 위해 정수 변수를 비트별로 조작할 수 있는 비트연산자를 사용한다.

두 정수 변수 또는 하나의 정수 변수를 이용하여 새로운 값을 만들어 내는 것이 목적이다.

 

1. AND 연산 : 둘다 켜져 있는 경우만 해당 비트를 켠다 (&)

2. OR 연산 : 둘 중 하나라도 켜져 있는 경우에 해당 비트를 켠다 (|)

3. XOR 연산 : 둘 중 하나만 켜져 있는경우에 해당 비트를 켠다 (^)

4. NOT 연산 : 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠다 (~)

5. 시프트 (shift) 연산

     - 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다 (<< >>)

     - 움직이고 나서 빈자리는 0으로 채워지게 된다.

 

 

가장 대표적인 예시인 집합 구현 문제이고, 여기서 "하나의 bit가 하나의 원소" 를 의미한다.

비트가 켜져 있으면 해당 원소가 집합에 포함되어 있다는 의미고, 꺼져 있으면 포함되어 있지 않다는 의미다.

N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있게 된다는 것이다.

 

기존에 N개의 boolean 원소를 갖는 배열을 선언해야 했지만,

비트마스크를 이용하면 정수 하나로 표현이 가능하기 때문에 사용하는 메모리의 크기가 줄어드는 것!

 

 

 

풀이

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

public class Main {
	static int bitmask = 0;
	static StringBuilder sb = new StringBuilder();

	public static void calculation(StringTokenizer st) {
		String cal = st.nextToken();
		int tmp;

		switch(cal) {
			case "add" : 
				tmp = Integer.parseInt(st.nextToken());
				bitmask |= (1 << tmp);
				break;
			case "remove" :
				tmp = Integer.parseInt(st.nextToken());
				bitmask &= ~(1 << tmp);
				break;
			case "check" :
				tmp = Integer.parseInt(st.nextToken());
				sb.append((bitmask & (1 << tmp)) != 0 ? "1\n" : "0\n");
				break;
			case "toggle" :
				tmp = Integer.parseInt(st.nextToken());
				bitmask ^= (1 << tmp);
				break;
			case "all" :
				bitmask |= ~0;
				break;
			case "empty" :
				bitmask &= 0;
				break;
		}
	}

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

		while(n-- != 0) {
			calculation(new StringTokenizer(br.readLine()));
		}

		System.out.println(sb);
	}
}

 

 

© 참고

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

https://rebro.kr/63

11723번: 집합