문제
비어 있는 공집합 S에 대해 M개의 연산을 수행한다. 연산은 add x, remove x, check x, toggle x, all, empty 6가지이며, 1부터 20까지의 정수를 원소로 갖는다. check x는 x가 S에 포함되면 1, 아니면 0을 출력한다. 연산이 최대 3,000,000회로 매우 많아 빠른 입출력과 효율적인 집합 표현이 필요하다.
입력
첫째 줄에 M이 주어진다. (1 ≤ M ≤ 3,000,000) 둘째 줄부터 M개의 줄에 연산이 주어진다.
출력
check 연산마다 결과를 한 줄에 출력한다.
예제
| 입력 | 출력 |
|---|---|
26 add 1 add 2 check 1 check 2 check 3 remove 2 check 1 check 2 toggle 3 check 1 check 2 check 3 all check 10 check 20 toggle 10 remove 20 check 10 check 20 empty check 1 toggle 1 check 1 toggle 1 check 1 toggle 20 | 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 1 |
풀이
원소 범위가 1~20으로 제한되어 있으므로 정수 하나의 비트를 집합으로 활용하는 비트마스킹 기법을 사용한다. 각 비트 연산은 O(1)이므로 3,000,000회 연산도 빠르게 처리된다.
- 정수
T를 집합 상태로 사용한다.T의 n번째 비트가 1이면 n이 집합 S에 포함된 것이다. add(n):T | (1 << n)— n번째 비트를 1로 설정한다.remove(n):T & ~(1 << n)또는T -= T & (1 << n)— n번째 비트를 0으로 설정한다.check(n):(T & (1 << n)) == (1 << n)— n번째 비트가 1인지 확인한다.toggle(n): check 결과에 따라remove또는add를 호출한다.all():T = 2097150(비트 1~20을 모두 1로 설정,(1 << 21) - 2).empty():T = 0— 모든 비트를 0으로 초기화한다.
핵심 아이디어: 120의 정수 집합은 20비트 정수 하나로 완전히 표현된다. 비트 OR은 원소 추가, 비트 AND는 원소 포함 검사, 비트 XOR은 toggle에 응용할 수 있다. 20이 모두 켜진 값이다.2097150 = 0b111111111111111111110은 비트 1
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day59BOJ11723집합비트마스킹구현 { // 11723 집합 비트마스킹 구현
static int T = 0;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int n = 0; n < N; n++) {
st = new StringTokenizer(br.readLine());
String act = st.nextToken();
int num = 0;
if (st.hasMoreTokens())
num = Integer.parseInt(st.nextToken());
switch (act) {
case "add":
add(num);
break;
case "remove":
remove(num);
break;
case "check":
check(num);
sb.append(check(num) ? 1 : 0).append("\n");
break;
case "toggle":
toggle(num);
break;
case "all":
all();
break;
case "empty":
empty();
break;
}
}
System.out.println(sb);
br.close();
}
private static int add(int n) {
T = T | 1 << n;
return T;
}
private static int remove(int n) {
T -= T & 1 << n;
return T;
}
private static boolean check(int n) {
return (T & 1 << n) == (1 << n);
}
private static void toggle(int n) {
T = check(n) ? remove(n) : add(n);
}
private static void all() {
T = 2097150;
}
private static void empty() {
T = 0;
}
}복잡도
- 시간: O(M) — M개의 연산 각각 O(1) 비트 연산 처리
- 공간: O(1) — 정수 하나로 집합 상태 관리