[해커랭크(HackerRank) JAVA 풀이] - Java BitSet

해커랭크 - https://www.hackerrank.com/
Prepare > Java > Data Structures > Java BitSet

HackerRank

 

Java의 BitSet 클래스는 필요에 따라 커지는 비트 값 벡터(즉, false(0) 또는 true(1))를 구현하므로 공간을 최적화하면서 비트를 쉽게 조작할 수 있습니다(다른 컬렉션과 비교할 때). 비트 값이 1인 모든 요소를 세트 비트라고 합니다.

두 BitSet의 모든 비트가 0으로 초기화되는 크기가 N인 2개의 BitSet인 B₁ 및 B₂가 주어지면 일련의 M 연산을 수행합니다. 각 작업 후에 각 BitSet의 설정된 비트 수를 새 줄에 공백으로 구분된 두 개의 정수로 인쇄합니다.

 

Input Format

첫 번째 줄에는 공백으로 구분된 2개의 정수, 각각 N(BitSet B₁ 및 B₂의 길이) 및 M(수행할 작업 수)이 포함됩니다.
M개의 후속 라인은 각각 다음 형식 중 하나의 작업을 포함합니다.

• AND <set> <set>
• OR <set> <set>
• XOR <set> <set>
• FLIP <set> <index>
• SET <set> <index>

위 목록에서 <set>은 정수 1 또는 2이며, 여기서 1은 B₁, B₂를 나타냅니다.
<index>는 <set>에 해당하는 BitSet에서 비트의 인덱스를 나타내는 정수이다.

이진 연산 AND, OR 및 XOR의 경우 피연산자는 왼쪽에서 오른쪽으로 읽고 연산의 결과인 BitSet은 첫 번째 피연산자의 내용을 대체합니다. 예를 들어:

AND 2 1

B₂는 왼쪽 피연산자이고 B₁는 오른쪽 피연산자입니다. 이 연산은 B₂ ∧ B₁의 결과를 B₂에 대입해야 한다.

 

Constraints

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 10000

 

Output Format

각 작업 후에 BitSet B₁ 및 BitSet B₂에 설정된 비트 수를 공백으로 구분된 2개의 정수로 새 줄에 출력합니다.

 

 

Sample Input

5 4
AND 1 2
SET 1 4
FLIP 2 2
OR 2 1

 

Sample Output

0 0
1 0
1 1
1 2

 

Explanation

Initially: N = 5, M = 4, B₁ = {0, 0, 0, 0, 0}, B₂ = {0, 0, 0, 0, 0}. 각 단계에서 B₁ 및 B₂의 각 세트 비트 수를 공백으로 구분된 정수 쌍으로 새 줄에 출력합니다.
M₀ = AND 1 2
B₁ = B₁ ∧ B₂ = {0, 0, 0, 0, 0} ∧ {0, 0, 0, 0, 0} = {0, 0, 0, 0, 0}
B₁ = {0, 0, 0, 0, 0}, B₂ = {0, 0, 0, 0, 0}
B₁과 B₂에 설정된 비트 수는 0입니다.
M₁ = SET 1 4
B₁[4]를 true(1)로 설정합니다.
B₁ = {0, 0, 0, 0, 1}, B₂ = {0, 0, 0, 0, 0}
B₁의 설정 비트 수는 1이고 B₂는 0입니다.
M₂ = FLIP 2 2
B₂[2]를 false(0)에서 true(1)으로 뒤집습니다.
B₁ = {0, 0, 0, 0, 1}, B₂ = {0, 0, 1, 0, 0}
B₁의 설정 비트 수는 1이고 B₂는 1입니다.
M₃ = OR 2 1
B₂ = B₂ ∨ B₁ = {0, 0, 1, 0, 0} ∨ {0, 0, 0, 0, 1} = {0, 0, 1, 0, 1}
B₁ = {0, 0, 0, 0, 1}, B₂ = {0, 0, 1, 0, 1}
B₁의 설정 비트 수는 1이고 B₂는 2입니다.

 

Code

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        BitSet[] B = new BitSet[2];
        B[0] = new BitSet(N);
        B[1] = new BitSet(N);
        
        int M = sc.nextInt();
        for(int i=0; i<M; i++) {
            String operation = sc.next();
            int x = sc.nextInt();
            int y = sc.nextInt();
            switch( operation ) {
                case "AND":  B[x-1].and(B[y-1]); break;
                case "OR":   B[x-1].or(B[y-1]); break;
                case "XOR":  B[x-1].xor(B[y-1]); break;
                case "FLIP": B[x-1].flip(y); break;
                case "SET":  B[x-1].set(y); break;
        }
        System.out.println( B[0].cardinality()+" "+B[1].cardinality() );
        }
    }
}

 

 

BitSet
비트 배열과 같은 데이터 구조.
각 비트를 저장하고 다양한 비트 조작 연산을 수행

BitSet의 특징과 사용법
1. 생성 및 초기화 (new BitSet())

BitSet bitSet = new BitSet();​

비어 있는 BitSet 객체를 생성. 필요에 따라 크기를 지정하여 생성 가능.


2. 비트 설정 (Set)

bitSet.set(index);​

특정 인덱스의 비트를 1로 설정.

3. 비트 비설정 (Clear)

 

bitSet.clear(index);​

특정 인덱스의 비트를 0으로 설정.

4. 비트 반전 (Flip)

bitSet.flip(index);​

특정 인덱스의 비트를 반전. (0인 경우 1로, 1인 경우 0으로)

5. 비트 가져오기 (Get)

boolean value = bitSet.get(index);​

특정 인덱스의 비트 값을 가져옴.

6. 비트 조작 연산 (AND, OR, XOR)

bitSet1.and(bitSet2);  // AND 연산
bitSet1.or(bitSet2);   // OR 연산
bitSet1.xor(bitSet2);  // XOR 연산​

BitSet 객체 간에 AND, OR, XOR 연산을 수행.

7. 카디널리티 (Cardinality)

int count = bitSet.cardinality();​

BitSet에 설정된 1의 개수를 반환.

8. 비트 검색 (Next Set Bit)

int index = bitSet.nextSetBit(fromIndex);​

지정한 인덱스 이후에서 처음으로 1로 설정된 비트의 인덱스를 반환.

9. 비트 검색 (Previous Set Bit)

int index = bitSet.previousSetBit(fromIndex);​

지정한 인덱스 이전에서 가장 나중에 1로 설정된 비트의 인덱스를 반환.

 

 

개인 공부를 위한 포스팅입니다.
모든 번역, 코드는 완벽하지 않을 수 있습니다.