비트 마스킹 (BitMasking) & 백준 13701 (중복 제거)

• 비트 마스킹이란?

정수의 이진수 표현을 자료구조로 쓰는 기법으로 0, 1로 true/false, on/off와 같은 상태를 나타내는 것이 가능하다.

 

• 비트 마스크의 장점

1. 빠른 수행시간 - 비트 마스킹은 bit연산이므로 거의 모든 연산이 O(1)의 시간 복잡도를 갖고 있다.

2. 간결한 코드 - 다양한 집합 연산을 비트 연산자를 이용하여 한 줄로 작성이 가능하다.

3. 작은 메모리 사용량 - 1bit로 상태 저장이 가능하므로 메모리 사용량이 적어 DP에 유리하다. 

 

• 비트 연산자

비트 연산자	논리	의미
&	AND	양쪽 비트가 모두 1인 경우에만 1, 나머지 모든 경우 0
|	OR	양쪽 비트가 모두 0인 경우에만 0, 나머지 모든 경우 1
^	XOR	양쪽 비트가 서로 다른 경우 1, 같은 경우 0
~	NOT	비트 반전 (0이면 1, 1이면 0)
<<	SHIFT	정수 a를 왼쪽으로 b비트 만큼 이동 (빈자리를 0으로 채움, MSB가 바뀌면 양수 <-> 음수)
>>		정수 a를 오른쪽으로 b비트 만큼 이동 (빈자리 최상위 비트(MSB)로 채움)
>>>		정수 a를 오른쪽으로 b비트 만큼 이동 (빈자리 0으로 채움)

 

• 비트 마스크로 집합 연산

연산	예시 코드	설명
공집합	변수 = ((1 << A) - 1);	0 반환
꽉 찬 집합		A의 개수만큼 비트 켜짐(1)
원소 추가	A |= (1 << k);	k번째 비트 켜기
원소 삭제	A &= ~(1 <<k);	k번째 비트 끄기
원소 포함 여부	A & (1 << k) == (1 << k)	집합 A에서 k 번째 비트의 켜짐, 꺼짐 확인
원소 토글	A ^= (1 << k);	k번째 비트 반전
두 집합 연산	A | B	집합 A와 집합 B의 합집합
	A & B	집합 A와 집합 B의 교집합
	A & -B	집합 A - 집합 B (차집합)
	A ^ B	집합 A와 집합 B의 합집합 - 교집합 (XOR)
집합의 크기	Integer.bitCount(A);	집합 A내 켜진 비트수 반환
최소 원소 찾기	변수 = A & (-A);	집합 A에서 켜져있는 비트 중 최소 비트 반환
최소 원소 삭제	A &= A-1;	집합 A에서 켜져있는 비트 중 최소 비트 끄기
부분 집합 순회	for (int i = A; i; i =((i - 1) & A) {}	집합 A의 부분집합 순회

 

• BitSet

BitSet은 java.util에 있는 자료구조로 원소가 0 또는 1인 배열처럼 사용되며 사용법은 다음과 같다.

 

1. 선언 및 초기화 

    BitSet set = new BitSet(size); (size입력 안하면 크기 64로 초기화)

 

2. n 번째 비트 추가

    set.set(n);

 

3. n 번째 비트 삭제

    set.clear(n);

 

4. n 번째 비트 반전

    set.flip(n):

 

5. 1비트의 개수 반환

   set.cardinality();

 

6. 교집합, 차집합, 합집합, 대칭 차집합 (= 합칩합 - 교집합)

    set1.and(set2)       - set1과 set2의 교집합을 set1에 저장        

    set1.andNot(set2) - set1과 set2의 차집합을 set1에 저장  

    set1.or(set2)          - set1과 set2의 합집합을 set1에 저장  

    set1.xor(set2)        - set1과 set2의 대칭 차집합을 set1에 저장  

 

• 백준 13701 (중복 제거)

문제

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 개수 N은 1 이상 500만 이하이다.

입력

첫째 줄에 A1, A2, ..., AN이 주어진다.

출력

B1, B2, ..., BN’을 출력한다.

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

13701번: 중복 제거

---

해당 문제를 Set 자료구조로 풀려면 메모리 제한 8MB에 걸리므로 비트 마스킹을 이용해 풀어야하는 문제이다.

int나 long을 사용하면 문제의 범위인 0 ~ 33554432의 모든 수를 표현할 수 없으므로 BitSet을 이용했다.

BitSet까지 설정한 후엔  while문으로 들어가 EOF까지 주어진 숫자를 받는다. 이때 숫자가 처음 나온 것이면 숫자에 대응하는 bit를 1로 바꿔주고 출력해준다.

만약 그렇지 않은 경우 그대로 다음으로 넘어가 위 과정을 반복한다.

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        BitSet set = new BitSet(33554432);
        while (st.hasMoreTokens()){
            int n = Integer.parseInt(st.nextToken());
            if (set.get(n)) continue;
            set.set(n);
            sb.append(n).append(" ");
        }
        System.out.println(sb);
    }
}

---

 

reference

-https://meal-coding.tistory.com/33

[백준 1269] 대칭 차집합 - JAVA

-https://kwin0825.tistory.com/143

[JAVA / 자바] 비트 마스킹(Bit Mask), BitSet자료형