22.5.06 [HackerRank]Java BitSet

서태욱·2022년 5월 6일
0

Algorithm

목록 보기
31/45
post-thumbnail

✅ 문제 분석

첫 줄에 B1 B2 길이를 나타내는 정수 n과 수행할 작업 수 m이 한칸 띄어 입력된다.
다음 줄부터는


위 다섯가지 형태 중 하나로 입력 된다.
set에서 1,2는 각각 B1, B2를 의미한다.
index의 숫자는 BitSet안의 비트 인덱스를 의미한다.

이진연산 AND OR XOR는 첫번째 피연산자에 두번째 피연산자의 집합을 적용한다.

예를 들어 AND 2 1인 경우 B2에 B1과 B2의 합집합이 들어간다.

M0 = AND 1(SET) 2(SET)

B1 = B1 ∩ B2 = {0,0,0,0,0} ∩ {0,0,0,0,0} = {0,0,0,0,0}
B1 ={0,0,0,0,0}, B2={0,0,0,0,0}
따라서 설정된 비트수가 각각 0이므로
0 0 이 출력됨

M1 = SET 1(SET) 4(INDEX)

SET으로 인덱스 값을 바꾼다.
1 4는 B1의 4번째 인덱스를 바꾸라는 뜻.
B1[4] 이므로, B1 = {0,0,0,0,1} B2 = {0,0,0,0,0}
따라서 각각 비트수는 1 0이 출력된다.

M2 = FLIP 2(SET) 2(INDEX)

Flip은 원래 값을 뒤집는다.
B2의 2번 인덱스를 뒤집는다.
B1 = {0,0,0,0,1} B2 = {0,0,1,0,0}
각각 비트수가 1, 1이 된다.

M3 = OR 2 1

B2 = B2 ∪ B1 = {0,0,1,0,0} ∪ {0,0,0,0,1} = {0,0,1,0,1}
각각 비트수는 1, 2가 된다.

🌱 배경지식

BitSet

Bit로 이루어진 vector로, boolean과 비슷하게 이용할 수 있다.
(예: false(0), true(1))

boolean은 값당 1byte(=8bit)지만 bitset은 1bit기 때문에
한 값당 7bit씩 아낄 수 있다.

디폴트값이 false(0)이다.

switch/case문

if문과 비슷하지만 좀 더 정형화 된 조건 판단문이다.

switch(입력변수) {
    case 입력값1: ...
         break;
    case 입력값2: ...
         break;
    ...
    default: ...
         break;
}

입력 변수 값과 일치하는 case 입력값이 있다면 해당 case에 적힌 문장이 실행된다.
break로 해당 case문을 실행한 뒤 switch문을 빠져나간다.

Java BitSet | cardinality()

cardinality 메소드는 BitSet에서 elements의 수를 반환해준다.

import java.util.*;
public class GFG {
    public static void main(String[] args)
    {
        // Constructors of BitSet class
        BitSet bs1 = new BitSet();
        BitSet bs2 = new BitSet();
        BitSet bs3 = new BitSet();
 
        /* set is BitSet class method
        explained in next articles */
        bs1.set(0);
        bs1.set(1);
        bs1.set(2);
        bs1.set(4);
 
        // assign values to bs2
        bs2.set(4);
        bs2.set(6);
        bs2.set(5);
        bs2.set(1);
        bs2.set(2);
        bs2.set(3);
 
        // Printing the 2 Bitsets
        System.out.println("bs1 : " + bs1);
        System.out.println("bs2 : " + bs2);
        System.out.println("bs3 : " + bs3);
 
        // Performing logical AND
        // on bs2 set with bs1
        System.out.println(bs1.cardinality());
        System.out.println(bs2.cardinality());
        System.out.println(bs3.cardinality());
    }
}

결과

bs1 : {0, 1, 2, 4}
bs2 : {1, 2, 3, 4, 5, 6}
bs3 : {}
4
6
0

✏️ 해설

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();
        int m = sc.nextInt();

        BitSet[] bitset = new BitSet[2]; //배열 길이가 2인 bitset 배열 생성
        bitset[0] = new BitSet(n); //배열의 0번 인덱스에 들어갈 값
        bitset[1] = new BitSet(n); //배열 1번 인덱스에 들어갈 값

        for(int i=0; i<m; i++) {
            String operation = sc.next(); //AND, OR 등등 입력
            int x = sc.nextInt(); 
            int y = sc.nextInt();
            switch( operation ) { switch/case문으로 bitset 메소드들을 실행한다. 
                case "AND":
                    bitset[x-1].and(bitset[y-1]);
                    break;
                case "OR":
                    bitset[x-1].or(bitset[y-1]);
                    break;
                case "XOR":
                    bitset[x-1].xor(bitset[y-1]);
                    break;
                case "FLIP":
                    bitset[x-1].flip(y);
                    break;
                case "SET":
                    bitset[x-1].set(y);
                    break;
            }
            System.out.println( bitset[0].cardinality()+" "+bitset[1].cardinality() ); //cardinality() 메소드로 각 bitset 배열의 요소 수를 세준다.
        }
    }
}

👉 참고

profile
re:START

0개의 댓글