[코드트리/INTERMEDIATE HIGH] bit 계산 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 비트마스크

- 시간 복잡도 : O(Q)

 

1) add 연산 , delete 연산 : 숫자  x가 집합 A에 들어가 있는지 확인

if(((S >> x) & 1) == 0)		// add 연산 : 집합에 없는 경우, 새로 추가
	S ^= (1 << x);
    
else if(((S >> x) & 1) == 1)	// delete 연산 : 이미 집합에 들어있는 수인 경우, 제거
	S ^= (1 << x);

 

 

2) print 연산 : 집합에 들어가 있는 수인 경우 1 출력/ 집합에 없는 수인 경우 0 출력

System.out.prinltn((S >> x) & 1);

 

3) toggle 연산 : 집합 S에 수가 있다면 제거, 없다면 추가

S ^= (1 << x);

 

4) clear 연산 : 공집합으로 만들기

S = 0;

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int q = Integer.parseInt(br.readLine());
        int S = 0;  // 비트마스크로 표현되는 집합
 
        while(q --> 0) {
            String[] str = br.readLine().split(" ");
            
            if(str[0].equals("add")) {
                int x = Integer.parseInt(str[1]);
 
                // x 번째 비트가 0인지 확인하고, 0이면 해당 비트를 1로 변경
                if(((S >> x) & 1) == 0)
                    S ^= (1 << x);
            }
            else if(str[0].equals("delete")) {
                int x = Integer.parseInt(str[1]);
 
                // x 번째 비트가 1인지 확인하고, 1이면 해당 비트를 0으로 변경
                if(((S >> x) & 1) == 1) {
                    S ^= (1 << x);
                }
            }
            else if(str[0].equals("print")) {
                int x = Integer.parseInt(str[1]);
 
                // x 번째 비트가 1인지 확인하여 결과를 StringBuilder에 추가
                sb.append((S >> x) & 1).append("\n");
            }
            else if(str[0].equals("toggle")) {
                int x = Integer.parseInt(str[1]);
                
                // x번째 비트 토글 (1이면 0으로, 0이면 1로)
                S ^= (1 << x);
            }
            else if(str[0].equals("clear")) {
                // 집합 비움 = 공집합 (모든 비트를 0으로 변경)
                S = 0;
            }
        }
 
        System.out.println(sb);
    }
}

 

 

 

➕ 다른 풀이 방식

- 492ms, 26MB

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        int q = Integer.parseInt(br.readLine());
        int S = 0;  // 비트마스크로 표현되는 집합
 
        while(q --> 0) {
            String[] str = br.readLine().split(" ");
            
            if(str[0].equals("add")) {
                int x = Integer.parseInt(str[1]);
 
                // x번째 비트가 0인지 확인하고, 0이면 해당 비트를 1로 변경
                if((S & (1 << x)) != (1 << x))
                   S ^= (1 << x);
            }
            else if(str[0].equals("delete")) {
                int x = Integer.parseInt(str[1]);
 
                // x번째 비트가 1인지 확인하고, 1이면 해당 비트를 0으로 변경
                if((S & (1 << x)) == (1 << x)) {
                   S ^= (1 << x);
                }
            }
            else if(str[0].equals("print")) {
                int x = Integer.parseInt(str[1]);
 
                // x번째 비트가 1인지 확인하여 결과를 StringBuilder에 추가
               sb.append((S & (1 << x)) == (1 << x) ? 1 : 0).append("\n");
            }
            else if(str[0].equals("toggle")) {
                int x = Integer.parseInt(str[1]);
                
                // x번째 비트 토글 (1이면 0으로, 0이면 1로)
               S ^= (1 << x);
            }
            else if(str[0].equals("clear")) {
                // 집합 비움 = 공집합 (모든 비트를 0으로 변경)
               S = 0;
            }
        }
 
        System.out.println(sb);
    }
}

 

 

---

💦 어려웠던 점

- 괄호를 잘 쳐주어야 한다.. 안 그러면 에러가 난다.

 

 

🧐 새로 알게 된 내용

- 비트마스크를 이용한 집합 구현과 숫자 추가,제거,토글 연산!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리

[알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java)