Problem Solving
[Java] Baekjoon Online Judge 11723: 집합
Isaac S. Lee
2023. 11. 13. 21:33
11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
💡문제
비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.
- add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
- remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
- check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
- toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
- all: S를 {1, 2, ..., 20} 으로 바꾼다.
- empty: S를 공집합으로 바꾼다.
✏️입력
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.
둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
📑출력
check 연산이 주어질때마다, 결과를 출력한다.
⏳메모리 제한
- Java 8: 448 MB
- Java 8 (OpenJDK): 448 MB
- Java 11: 448 MB
- Kotlin (JVM): 448 MB
- C#: 64 MB
- Java 15: 448 MB
- F#: 64 MB
- Visual Basic: 64 MB
예제입력 1
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
check 4
all
check 10
check 20
toggle 10
remove 20
check 10
check 20
empty
check 1
toggle 1
check 1
toggle 1
check 1
예제출력 1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
🔎알고리즘 분류
- 구현
- 비트마스킹
📌풀이
코드 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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()); // 연산의 수
boolean[] set = new boolean[21]; // 집합을 나타내는 배열 (인덱스 1부터 사용)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
String[] operation = br.readLine().split(" ");
switch (operation[0]) {
case "add":
add(set, Integer.parseInt(operation[1]));
break;
case "remove":
remove(set, Integer.parseInt(operation[1]));
break;
case "check":
sb.append(check(set, Integer.parseInt(operation[1]))).append('\n');
break;
case "toggle":
toggle(set, Integer.parseInt(operation[1]));
break;
case "all":
all(set);
break;
case "empty":
empty(set);
break;
}
}
System.out.println(sb);
}
static void add(boolean[] set, int x) {
set[x] = true;
}
static void remove(boolean[] set, int x) {
set[x] = false;
}
static int check(boolean[] set, int x) {
return set[x] ? 1 : 0;
}
static void toggle(boolean[] set, int x) {
set[x] = !set[x];
}
static void all(boolean[] set) {
for (int i = 1; i <= 20; i++) {
set[i] = true;
}
}
static void empty(boolean[] set) {
for (int i = 1; i <= 20; i++) {
set[i] = false;
}
}
}
코드 2
import java.io.DataInputStream;
import java.io.IOException;
public class Main {
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return neg ? -ret : ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din != null)
din.close();
}
}
public static void main(String[] args) throws IOException {
Reader in = new Reader();
StringBuilder out = new StringBuilder();
int M = in.nextInt();
int bit = 0, cnt = 0;
while (M-- > 0) {
char operation = (char) in.read();
switch (operation) {
case 'a':
if (in.read() == 'd') {
in.read();
bit |= 1 << in.nextInt() - 1;
} else {
in.read(); in.read();
bit = (1 << 20) - 1;
}
break;
case 'r':
in.read(); in.read(); in.read(); in.read(); in.read();
bit &= ~(1 << in.nextInt() - 1);
break;
case 'c':
in.read(); in.read(); in.read(); in.read();
out.append((bit & 1 << in.nextInt() - 1) != 0 ? 1 : 0).append('\n');
if (++cnt == 100000) {
cnt = 0;
System.out.print(out);
out.setLength(0);
}
break;
case 't':
in.read(); in.read(); in.read(); in.read(); in.read();
bit ^= 1 << in.nextInt() - 1;
break;
default:
in.read(); in.read(); in.read(); in.read(); in.read();
bit = 0;
break;
}
}
System.out.print(out);
in.close();
}
}
코드 3
import java.io.DataInputStream;
import java.io.IOException;
public class Main {
// 입력을 빠르게 받기 위한 Reader 클래스
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
// 생성자에서 필요한 초기화 작업
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
// 다음 정수를 읽어오는 메서드
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
// 공백 문자 무시
while (c <= ' ') {
c = read();
}
// 음수 여부 확인
boolean neg = (c == '-');
if (neg)
c = read();
// 숫자로 변환
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
// 음수인 경우 처리
return neg ? -ret : ret;
}
// 버퍼를 채우는 메서드
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
// 버퍼에서 한 바이트씩 읽어오는 메서드
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
// 스트림을 닫는 메서드
public void close() throws IOException {
if (din != null)
din.close();
}
}
public static void main(String[] args) throws IOException {
// Reader 객체 생성
Reader in = new Reader();
// 출력 결과를 저장하기 위한 StringBuilder 객체 생성
StringBuilder out = new StringBuilder();
// 연산의 수를 입력 받음
int M = in.nextInt();
// 비트 연산에 사용할 변수 초기화
int bit = 0;
// 출력 횟수를 관리하는 변수 초기화
int cnt = 0;
// 연산의 수만큼 반복
while (M-- > 0) {
// 다음 연산의 종류를 문자로 읽어옴
char operation = (char) in.read();
// 각 연산 종류에 따라 처리
switch (operation) {
case 'a': // add 또는 all 연산
if (in.read() == 'd') { // add 연산
in.read(); // 공백 문자 무시
// 해당 비트를 1로 설정
bit |= 1 << in.nextInt() - 1;
} else { // all 연산
in.read(); in.read(); // 두 개의 문자를 무시하여 'll'을 처리
// 모든 비트를 1로 설정
bit = (1 << 20) - 1;
}
break;
case 'r': // remove 연산
in.read(); in.read(); in.read(); in.read(); in.read(); // 다섯 개의 문자를 무시하여 'emove'를 처리
// 해당 비트를 0으로 설정
bit &= ~(1 << in.nextInt() - 1);
break;
case 'c': // check 연산
in.read(); in.read(); in.read(); in.read(); // 네 개의 문자를 무시하여 'heck'를 처리
// 해당 비트가 1이면 1, 아니면 0을 출력
out.append((bit & 1 << in.nextInt() - 1) != 0 ? 1 : 0).append('\n');
// 출력이 100,000번마다 출력 버퍼를 비우기
if (++cnt == 100000) {
cnt = 0;
System.out.print(out);
// StringBuilder 초기화
out.setLength(0);
}
break;
case 't': // toggle 연산
in.read(); in.read(); in.read(); in.read(); in.read(); // 다섯 개의 문자를 무시하여 'oggle'을 처리
// 해당 비트가 1이면 0으로, 0이면 1로 변경
bit ^= 1 << in.nextInt() - 1;
break;
default: // empty 연산
in.read(); in.read(); in.read(); in.read(); in.read(); // 다섯 개의 문자를 무시하여 'mpty'를 처리
// 모든 비트를 0으로 설정
bit = 0;
break;
}
}
// 출력 결과를 출력
System.out.print(out);
// Reader를 닫음
in.close();
}
}