비트마스크
집합에는 1부터 20까지의 정수만 들어가므로 하나의 int에 원소의 포함 여부를 저장할 수 있습니다. 값 x를 비트 위치 x - 1에 대응시킵니다. 1 << (x - 1)은 해당 비트만 1인 마스크를 만듭니다. 시프트 위치는 0부터 시작하므로 값에서 1을 빼야 합니다. 전체 집합 마스크 (1 << 20) - 1은 하위 20비트가 모두 1이며, 0은 빈 집합입니다.
add는 마스크를 OR하여 원소를 포함시키고, remove는 마스크의 반전값과 AND하여 원소를 제거합니다. check는 AND 결과가 0이 아닌지 확인하며, toggle은 XOR로 해당 비트를 뒤집습니다. all은 전체 집합 마스크를 대입하고 empty는 집합을 비웁니다. 입력에서 원소를 사용하는 명령의 x는 1 <= x <= 20을 만족합니다. add와 remove는 원소가 이미 원하는 상태여도 안전합니다. 각 명령은 O(1) 시간, 집합은 O(1) 공간을 사용합니다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static final int FULL_SET = (1 << 20) - 1;
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int commandCount = input.nextInt();
int set = 0;
StringBuilder output = new StringBuilder();
for (int i = 0; i < commandCount; i++) {
String command = input.next();
if (command.equals("all")) {
set = FULL_SET;
} else if (command.equals("empty")) {
set = 0;
} else {
int x = input.nextInt();
int mask = 1 << (x - 1);
switch (command) {
case "add":
set |= mask;
break;
case "remove":
set &= ~mask;
break;
case "check":
output.append((set & mask) != 0 ? 1 : 0).append('\n');
break;
case "toggle":
set ^= mask;
break;
}
}
}
System.out.print(output);
}
private static final class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int length;
private int position;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) {
return -1;
}
}
return buffer[position++];
}
String next() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
StringBuilder token = new StringBuilder();
while (c > ' ') {
token.append((char) c);
c = read();
}
return token.toString();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
}