[백준] 11723번 집합(Java)

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

11723번: 집합

 

처음에는 집합이라는 단어를 보고 자바의 Set을 사용하여 문제를 풀어야겠다는 생각이 들었다.

그러나 계속 시간초과가 발생해서 찾아보니 비트마스크를 사용하여 풀 수 있음을 알게되었다.

 

Bitmask(비트마스크)

데이터의 특정 비트를 사용하여 특정 상태를 나타내거나 저장하는 기술

주로 플래그를 설정하거나 집합을 나타내는 데 사용됨

 

• 장점 
  • 수행 시간이 빠름
  • 간결한 코드
  • 메모리 사용량이 적음

비트 연산자: AND(&), OR(|), XOR(^), NOT(~), shift(<<, >>)

 

비트마스크를 이용한 집합

하나의 bit가 하나의 원소를 의미 = N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현 가능

ex. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}이라면  0~9라고 고려하여 문제를 풀어야 함 (-1한 값)

• 공집합
  • A = 0
  • ex. 0000000000
• 전체집합
  • A = (1 << 원소의_개수) -1
  • ex. 1111111111
• 원소 추가
  • A |= (1 << k)
  • ex. 원소가 5일 때 k=4이면 100000
• 원소 삭제
  • A &= ~(1 << k)
  • ex. A = 1111111111, 원소가 5일 때 k=4이면 1111101111
• 원소의 포함 여부 확인
  • if (A & (1 << k))
• 원소의 토글
  • A ^= (1 << k)
  • ex. k=4일 때 1111101111 <-> 111111111
• 집합연산자
  • 합집합: A | B
  • 교집합: A & B
  • 차집합: A & (~B)
  • A와 B 중 하나에만 포함된 원소들의 집합: A ^ B
• 집합의 크기 구하기 (비트 1의 개수)
  • Integer.bitCount(A)
• 최소 원소 찾기
  • A & (-A)
  • ex. A = 0001100100, -A = 11111111111111111111111110011100, A & (-A) = 100
• 최소 원소 지우기
  • A &= (A-1)
  • A에서 1을 빼주게 되면 가장 오른쪽에 있던 bit는 0이 되고 그보다 오른쪽에 있는 모든 bit들이 1이 되기 때문 

 

문제 풀이

1~20의 원소 전체 집합을 0b111111111111111111110으로 놓고 풀었다.

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

public class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N;
    static int ALL = 0b111111111111111111110;;

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

        N = stoi(st.nextToken());
        int betset = 0;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();

            switch (cmd) {
                case "add" :
                    betset |= 1 << stoi(st.nextToken());
                    break;
                case "remove" :
                    betset &= ~(1 << stoi(st.nextToken()));
                    break;
                case "check" :
                    if((betset & (1 << stoi(st.nextToken()))) != 0) sb.append("1\n");
                    else sb.append("0\n");
                    break;
                case "toggle" :
                    int a = stoi(st.nextToken());
                    if((betset & (1 << a)) != 0) betset &= ~(1 << a);
                    else betset |= 1 << a;
                    break;
                case "all" :
                    betset = ALL;
                    break;
                case "empty" :
                    betset = 0;
                    break;
            }
        }

        System.out.println(sb);
    }
}

 

 

참고

https://rebro.kr/63

비트마스크 (BitMask) 알고리즘