https://www.acmicpc.net/problem/11723
문제
문제 그대로 공집합 S에 아래 연산을 수행한다.
- add x : S에 x를 추가 (S에 x가 이미 있는 경우에는 연산을 무시)
- remove x : S에서 x를 제거 (S에 x가 없는 경우에는 연산을 무시)
- check x : S에 x가 있으면 1을, 없으면 0을 출력
- toggle x : S에 x가 있으면 x를 제거, 없으면 x를 추가
- all : S를 {1, 2, ..., 20} 으로 변경
- empty : S를 공집합으로 변경 (S를 비운다)
조건
- 1 ≤ x ≤ 20
빨간색 마킹표시를 정리하면 아래 내용과 같다.
- S에 x를 추가
- S에서 x를 제거
- S에 x가 있는지 없는지 유무 확인
위 기능들을 보면 자바에서 떠오르는 자료구조들이 있을 것이다.
Collection의 List, Set 이 있고 Map도 위 기능들을 수행할 수 있다.
주어진 값들을 키 - 값 구조로 넣을 필요는 없으니 Map은 제외하고, 주어진 연산의 수의 최댓값이 300만이니 List보다 속도가 빠른 Set으로 구현해보겠다.
사실 처음에 Set으로 구현하면 풀겠다 라고 생각했지만 로직을 잘못 구현해 자꾸 시간초과가 났었다.
그래서 문제의 힌트인 비트마스킹으로 풀었고, Set으로도 다시 풀어서 성공했다.
총 2가지 방법으로 풀이했다.
문제풀이
방법 1 - 비트마스킹
비트마스킹은 정수의 이진수 표현을 자료구조로 쓰는 기법이다.
먼저 비트연산자를 알아보자.
| 비트 연산 | 자바 비트 연산 | 설명 |
| AND | & | 대응하는 두 비트가 모두 1이면 1 |
| OR | | | 대응하는 두 비트 중 하나라도 1이면 1, 아니면 0 |
| XOR | ^ | 대응하는 두 비트가 다르면 1, 같으면 0 |
| NOT | ~ | 비트의 값을 반전 |
| SHIFT | <<. >> | 비트를 왼쪽 또는 오른쪽으로 이동 |
이제 이진수 표현을 자료구조로 어떻게 사용하는지 알아보자.
int는 4바이트 자료형이다. 4바이트 = 32비트 = 2³²
그리고 x는 1 ~ 20 범위의 정수다.
int로 표현할 수 있는 값은 2³² 0000 0000 0000 0000 0000 0000 0000 0000 으로 표현할 수 있다.
여기서 1 ~ 20 범위인 x를 위의 2진수에서 각 자리수를 x와 매칭시켜 아래 그림처럼 표현할 수 있다.
그럼 2진수인 형태에서 연산을 수행하면 아래와 같다.
x = 1 이라고 가정한다.
- add x : S에 x를 추가 (S에 x가 이미 있는 경우에는 연산을 무시)
- 자바 비트 연산 : S |= (1 << x)
- 1을 x만큼 왼쪽으로 이동 후 S의 x자리와 OR 연산
- remove x : S에서 x를 제거 (S에 x가 없는 경우에는 연산을 무시)
- 자바 비트 연산 : S &= ~(1 << x)
- 1을 x만큼 왼쪽으로 이동 후 반전시키면 0이 됨. 0과 S의 x자리와 AND 연산
- check x : S에 x가 있으면 1을, 없으면 0을 출력
- 자바 비트 연산 : (S & (1 << x)) != 0
- 1을 x만큼 왼쪽으로 이동 후 S의 x자리와 AND 연산 후 값이 1이면 있는 것이고 0이면 없는 것
remove 하여 1이 제거되었으니 0을 출력
- toggle x : S에 x가 있으면 x를 제거, 없으면 x를 추가
- 자바 비트 연산 : S ^= (1 << x)
- 1을 x만큼 왼쪽으로 이동 후 S의 x자리와 XOR 연산 (S의 x자리에 값이 있다면 0으로 변환(제거), 없다면 1로 변환(추가))
- all : S를 {1, 2, ..., 20} 으로 변경
- 자바 비트 연산 : S = (1 << 21) - 1;
- 1을 21만큼 왼쪽으로 이동 후 1을 빼게되면, 10 0000 0000 0000 0000 에서 1을 빼는 것이니 1부터 20자리까지 1로 변환됨
- empty : S를 공집합으로 변경 (S를 비운다)
- 자바 비트 연산 : S = 0
- S에 0을 대입하면 모든 자리가 0으로 변환됨
비트 연산만 이해되면 바로 풀 수 있다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
int m = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
// 공집합 S
int set = 0;
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
String op = st.nextToken();
if(op == null || op.isBlank()) continue;
int value = 0;
if(!op.equals("all") && !op.equals("empty")) {
value = Integer.parseInt(st.nextToken());
}
switch (op) {
case "add":
set |= (1 << value);
break;
case "remove":
set &= ~(1 << value);
break;
case "check":
sb.append((set & (1 << value)) != 0 ? 1 : 0).append("\n");
break;
case "toggle":
set ^= (1 << value);
break;
case "all":
// 1~20 의 수를 표현해야 되기때문에 21자리로 시트프 후 -1을 해서 20자리를 맞춤
set = (1 << 21) - 1;
break;
case "empty":
set = 0;
break;
}
}
System.out.println(sb);
} catch(Exception e) {}
}
}
방법 1 - Set 이용
문제에서 주어진 연산들을 모두 Set이 가지고 있기 때문에 Set을 이용하면 간단하다.
혹시 Set에 대해 아직 잘 모른다면 Set에 대해 조금 더 학습을 한 후 풀어보면 좋을 것 같다.
풀이는 간단하니 주석으로 대체하겠다.
import java.io.BufferedReader;
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) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
try {
int m = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
// 공집합 S
Set<Integer> set = new HashSet<>();
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
String op = st.nextToken();
// all이나 empty 연산은 값이 안 들어오기 때문에 예외처리 필요
int value = st.hasMoreTokens() ? Integer.parseInt(st.nextToken()) : 0;
switch (op) {
case "add":
// S에 x 추가
set.add(value);
break;
case "remove":
// S에서 x 제거
set.remove(value);
break;
case "check":
// S에 x가 있으면 1을, 없으면 0을 출력 (삼항 연산자)
sb.append(set.contains(value) ? 1 : 0).append("\n");
break;
case "toggle":
// S에 x가 있으면 x를 제거
if(set.contains(value)) set.remove(value);
// S에 x가 없으면 x를 추가
else set.add(value);
break;
case "all":
// S를 초기화
set.clear();
// 반복문을 통해 S에 {1, 2, ..., 20} 추가
for(int j=1; j<=20; j++) {
set.add(j);
}
break;
case "empty":
// S를 초기화
set.clear();
break;
}
}
System.out.println(sb);
} catch(Exception e) {}
}
}