[Java] BitSet

BitSet

• BitSet은 비트들로 이루어진 백터이고, 각 비트는 인덱스를 통해 개별적으로 접근할 수 있다. 이러한 점에서 boolean 배열과 유사하다. 
• 동적으로 크기를 확장할 수도 있으며, 필요에 따라서 더 많은 비트를 저장하기 위해 자동으로 크기를 조정한다.
• 초기값은 false.
• 메소드들은 여기서: https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html

---

BitSet vs. boolean 배열

• boolean 배열의 각 boolean 값은 1비트가 아닌 1바이트를 사용한다. 이는 컴퓨터가 다룰 수 있는 정보의 최소 단위가 바이트이기 때문.
• BitSet 클래스는 비트 단위의 연산을 지원하여, 비트 레벨에서 빠른 연산을 수행할 수 있도록 해준다. 이는 boolean 배열로는 직접적으로 지원되지 않는 기능이다.  
  
  특정 API와의 호환성을 제외하면 효율성으로는 BitSet이 더 뛰어나 보인다. 열심히 찾아보니 boolean 배열의 장점을 "직관적이고 구현이 간단하다"라고 하는 글들이 많지만, BitSet도 이미 구현된 메소드를 갖다 쓰는 것이라 크게 와닿지는 않았다. (결론은 BitSet 짱짱맨?)

---

적용 문제

 

 

이 문제처럼 메모리가 빡빡한 경우 BitSet을 사용할 수 있다.

 

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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		BitSet bset = new BitSet(1 << 25);

		while (st.hasMoreTokens()) {
			int A = Integer.parseInt(st.nextToken());
			if (!bset.get(A)) {
				sb.append(A).append(' ');
				bset.set(A);
			}
		}

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