728x90
11723 - 집합
https://www.acmicpc.net/problem/11723

문제
비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램
- add x: S에 x 추가
- remove x: S에서 x 제거
- check x: S에 x가 있으면 1/ 없으면 0 출력
- toggle x: S에 x가 있으면 x를 제거/ 없으면 0 출력
- all: S를 {1, 2, ..., 20}으로 바꿈
- empty: S를 공집합으로 바꿈
(1 <= x <= 20)
입력
첫째 줄: 수행해야 하는 연산의 수 M (1 <= M <= 3,000,000)
둘째 줄 ~ M개의 줄: 수행해야 하는 연산
출력: check 연산 주어질때마다, 결과 출력
풀이
숫자 1 ~ 20 저장
전등 켜져 있으면 숫자가 집합에 있음 / 꺼져 있으면 집합에 없음
ex. {1, 3} -> 전등 상태: 1(3) 0(2) 1(1) => 2진수: 101 / 10진수: 5
-> 숫자 하나로 집합 표현
- `1 << x`: 1을 왼쪽으로 x칸 이동 => $2^x$
- x번째 전등 하나만 켠 숫자
- ex. 1 << 3 = 00001000 => 3번 전등만 켜짐
- x번째 전등 하나만 켠 숫자
- ex. 1 << 0 = 00000001 (1) / 1 << 1 = 00000010 (2)
/ 1 << 2 = 00000100 (4) / 1 << 3 = 00001000 (8)
- add: `set |= (1 << x)`
- `|`: OR
- 이미 켜져 있으면 그대로 유지/ 꺼져 있으면 켜짐
- remove: `set &= ~(1 << x)`
- ~: NOT / `&`: AND
- 그 전등만 켜진 상태 만들고 뒤집기 = 그 전등만 꺼져 있고 나머지 켜짐
+ AND -> 그 번호 비트가 꺼짐
- check: `(set & (1 << x)) != 0`
- `&`: AND
- 0이 아니면 비트 켜져 있음
- toggle: `set ^= (1 << x)`
- `^`: XOR -> 1 ^ 1 = 0 / 0 ^ 1 = 1 => 비트 반전
- 켜져 있으면 끄고 꺼져 있으면 켬
- `all`: `set = (1 << 21) - 2`
- 1 ~ 20만 사용 -> 1 << 21 = 1000000000000000000000
-> -1하면 0111111111111111111111/ -2하면 0111111111111111111110
=> 1 ~ 20번 비트만 1
- 1 ~ 20만 사용 -> 1 << 21 = 1000000000000000000000
코드
import java.io.*;
import java.util.*;
// 집합
public class boj_11723 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int M = Integer.parseInt(br.readLine());
int set = 0;
while (M-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
String cmd = st.nextToken();
if (cmd.equals("add")) {
int x = Integer.parseInt(st.nextToken());
set |= (1 << x);
} else if (cmd.equals("remove")) {
int x = Integer.parseInt(st.nextToken());
set &= ~(1 << x);
} else if (cmd.equals("check")) {
int x = Integer.parseInt(st.nextToken());
sb.append((set & (1 << x)) != 0 ? 1 : 0).append("\n");
} else if (cmd.equals("toggle")) {
int x = Integer.parseInt(st.nextToken());
set ^= (1 << x);
} else if (cmd.equals("all")) {
set = (1 << 21) - 2;
} else if (cmd.equals("empty")) {
set = 0;
}
}
System.out.print(sb);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Two Pointers] 백준 1253 - 좋다 (Java) (0) | 2026.02.22 |
|---|---|
| [BOJ/비트] 백준 1182 - 부분수열의 합 (Java) (0) | 2026.02.16 |
| [BOJ/Segment Tree] 백준 2268 - 수들의 합 7 (Java) (0) | 2026.02.16 |
| [BOJ/Merge Sort] 백준 1517 - 버블 소트 (Java) (0) | 2026.01.15 |
| [BOJ/DFS] 백준 3109 - 빵집 (Java) (0) | 2026.01.13 |