문제
문제 설명
1부터 20까지가 가능한 공집합 S가 주어졌을 때 주어지는 연산을 수행하는 문제이다.
옛날에 풀었던 문제인데 그 때 풀때는 자료구조 Set을 이용해서 풀었는데 이번에는 비트마스킹 을 이용해서 풀어보려고 한다.
첫번째 구현(HashSet 이용)
import java.io.*;
import java.util.*;
import java.util.stream.*;
public class Main {
private static Set<Integer> set = new HashSet<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int loop = Integer.parseInt(br.readLine());
while(loop-- > 0) {
String[] operators = br.readLine().split(" ");
String operator = operators[0];
if(operators.length != 1) {
int operand = Integer.parseInt(operators[1]);
switch(operator) {
case "add" :
add(operand);
break;
case "remove":
remove(operand);
break;
case "check":
bw.write(check(operand) + "\n");
break;
case "toggle":
toggle(operand);
break;
default:
break;
}
}else {
switch(operator) {
case "all":
all();
break;
case "empty":
empty();
break;
default:
break;
}
}
}
bw.flush();
bw.close();
}
private static void add(int value) {
set.add(value);
}
private static void remove(int value) {
if(set.contains(value)) set.remove(value);
}
private static int check(int value) {
if(set.contains(value)) return 1;
else return 0;
}
private static void toggle(int value) {
if(set.contains(value)) {
remove(value);
}else {
add(value);
}
}
private static void all() {
IntStream.range(1, 21).forEach(i -> add(i));
}
private static void empty() {
set.clear();
}
}위의 코드를 보면 알겠지만 단순히 그냥 자료구조에다가 연산을 차례대로 해주었다.
두번째 구현(비트마스킹 이용)
이번엔 비트마스킹을 활용해보자.
이 문제에서는 총 20개의 숫자의 유무를 저장해야하는데 int 자료형은 32bit 정수이기 때문에 변수 1개면 32개를 표현할 수 있기 때문에 bit 라는 변수를 선언하여 풀었다.
이제 연산을 하나하나 살펴보며 비트마스킹이 어떻게 활용되는지 봐야한다.
add 연산
add 연산이 들어오면 다음 변수인 x를 집합에 추가해주어야 한다.
x가 3이라고 쳤을 때 비트를 x - 1 번 left shift 연산을 해주고 OR 연산을 통해 해당 비트가 켜지게 되는 원리이다.
코드로는 다음과 같다.
case "add":
x = Integer.parseInt(st.nextToken());
bit |= (1 << (x - 1));
break;remove 연산
remove 연산에서는 x를 제거하는 연산이다.
add 연산과 비슷하게 생각하면 되는데 x 번째 비트를 끄고 나머지는 전부 1인 상태에서 & 여산을 해주면 된다.
case "remove":
x = Integer.parseInt(st.nextToken());
bit &= ~(1 << (x - 1));
break;check 연산
check 연산에서는 위와 같은 방식으로 x 번째 비트가 켜져있는지 확인하면 된다.
case "check":
x = Integer.parseInt(st.nextToken());
sb.append((bit & (1 << (x - 1))) != 0 ? "1\n" : "0\n");
break;toggle 연산
toggle 연산에서는 x 번째 비트의 결과를 반전시키면 되기 때문에 XOR 연산을 통해 현재비트를 키거나 끌 수 있다.
case "toggle":
x = Integer.parseInt(st.nextToken());
bit ^= (1 << (x - 1));
break;all 연산
all 연산에서는 모든 비트를 켜주면 되기 때문에 모든 숫자를 1로 바꾸면 된다.
case "all":
bit |= (~0);
break;empty 연산
empty에서는 모든 숫자를 0으로 바꾸면 된다.
case "empty":
bit &= 0;
break;이런식으로 구현하면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_11723 {
static int m;
static int[] arr;
static int bit = 0;
static int x;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
m = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
arr = new int[20];
for (int i = 0; i < m; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
switch(cmd) {
case "add":
x = Integer.parseInt(st.nextToken());
bit |= (1 << (x - 1));
break;
case "remove":
x = Integer.parseInt(st.nextToken());
bit &= ~(1 << (x - 1));
break;
case "check":
x = Integer.parseInt(st.nextToken());
sb.append((bit & (1 << (x - 1))) != 0 ? "1\n" : "0\n");
break;
case "toggle":
x = Integer.parseInt(st.nextToken());
bit ^= (1 << (x - 1));
break;
case "all":
bit |= (~0);
break;
case "empty":
bit &= 0;
break;
}
}
System.out.println(sb);
}
}
개미는 오늘도 일을 합니다.