[Java] 백준 11723번 - 집합

https://www.acmicpc.net/problem/11723

11723번: 집합

 

 

접근 방법

 

문제를 보자마자 떠오르는 방법은 HashSet 자료 구조를 이용하는 것이었다. 그래서 먼저 HashSet으로 문제를 해결 한 후, 비트마스킹을 학습하고자 리팩토링 해보았다.

 

 

 

 

 

 

HashSet

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine());
		
		StringBuffer sb = new StringBuffer();
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String command = st.nextToken();
			int input = -1;
			
			switch(command) {
			case "add":
				set.add(Integer.parseInt(st.nextToken()));
				break;
			case "remove":
				set.remove(Integer.parseInt(st.nextToken()));
				break;
			case "check":
				input = Integer.parseInt(st.nextToken());
				if (set.contains(input)) {
					sb.append(1);
				} else {
					sb.append(0);
				}
				sb.append("\n");
				break;
			case "toggle":
				input = Integer.parseInt(st.nextToken());
				if (set.contains(input)) {
					set.remove(input);
				} else {
					set.add(input);
				}
				break;
			case "all":
				set = new HashSet<>();
				for (int j = 1; j <= 20; j++) {
					set.add(j);
				}
				break;
			case "empty":
				set.clear();
				break;
			}
		}
		System.out.print(sb.toString());
	}
}

 

해당 코드에서 HashSet 자료 구조를 이용하는 부분만 비트마스킹으로 변경하였다.

 

 

 

 

 

 

비트마스킹 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine());
		
		StringBuffer sb = new StringBuffer();
		int set = 0;
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String command = st.nextToken();
			
			int input = -1;
			switch(command) {
			case "add":
				input = Integer.parseInt(st.nextToken());
				set = set | (1 << input);
				break;
			case "remove":
				input = Integer.parseInt(st.nextToken());
				set = set & ~(1 << input);
				break;
			case "check":
				input = Integer.parseInt(st.nextToken());
				sb.append(((set & (1 << input)) > 0) ? "1\n" : "0\n");
				break;
			case "toggle":
				input = Integer.parseInt(st.nextToken());
				set = set ^ (1 << input);
				break;
			case "all":
				set = (1 << 21) - 1;
				break;
			case "empty":
				set = 0;
				break;
			}
		}
		System.out.print(sb.toString());
	}
}

 

 

 

input된 숫자를 그대로 사용하기 위해 최하위 비트인 LSB는 더미 데이터로 사용하였다.

 

 

 

1. add

 

설명을 위해 set을 4비트의 1000(2)로 가정해보겠다.

input이 2라고 들어왔을 때

1은 0001(2)이므로, 1 << input 은 0100(2)이 된다. 

 

원소 Idx	3	2	1	0
set	1	0	0	0
1 << Input	0	1	0	0
set | (1 << Input)	1	1	0	0

 

이 상태에서 1000(2) | 0100(2)의 비트연산을 하면, idx가 2인 원소를 제외하고는 원래 값이 유지가 되면서 idx2는 반드시 1이 되게 된다.

 

 

 

 

2. remove

 

1 << input(=2)을 비트 부정 연산자를 이용해 1의 보수를 구하면 1011(2)가 된다.

원소 Idx	3	2	1	0
set	1	1	0	0
~ (1 << Input)	1	0	1	1
set &  ~(1 << Input)	1	0	0	0

 

원래의 set과 &연산을 시키면 idx2는 무조건 0이 되므로, 해당 비트에 해당하는 원소가 remove 되었다고 볼 수 있다.

 

 

 

 

 

3. check

 

원소 Idx	3	2	1	0
set	1	0	0	0
1 << Input	0	1	0	0
set & (1 << Input)	0	0	0	0

 

체크할 idx가 2일 경우,  1 << 2와 &연산을 시키면 set에 따라 0100 혹은 0000이 나오게 된다.

즉 idx n이 set에 포함되어 있을 경우 &연산의 결과가 항상 0보다 크므로 이를 기준으로 삼는다. 

 

 

 

 

4. toggle

 

원소 Idx	3	2	1	0
set	1	1	0	0
1 << Input	0	1	0	0
set ^ (1 << input)	1	0	0	0

 

toggle의 경우, set의 idx2가 1일 경우 0이 되어야하고 0일 경우 1이 되어야한다.

즉 비트의 관점에서 봤을 때 1과 xor 연산이 필요하다.

 

 

 

 

5. all

 

set의 모든 비트를 1로 만들어줘야하므로 set이 n비트일 경우, (1 << n+1) - 1을 해준다.

1 << 5는 10000(2)인데, 여기서 1을 빼면 1111(2)이 되기 때문이다. int타입일 경우 정확히는 0000_0000_0000_0000_ 0000_0000_0000_1111(2)이겠지만 우리는 4비트까지만 신경쓸 것이므로 상관하지 않아도 된다.

 

 

 

 

6. empty

 

모든 비트를 0으로 초기화 해주어야 하므로 set = 0이다.