[Java] baekjoon_11723 : 집합
구현, 비트마스킹
집합 : Silver5
https://www.acmicpc.net/problem/11723
11723번: 집합
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
www.acmicpc.net
첫 번째 작성 코드
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int M = Integer.parseInt(br.readLine());
ArrayList<Integer> S = new ArrayList<>();
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String input = st.nextToken();
int num = 0;
switch (input) {
case "add":
num = Integer.parseInt(st.nextToken());
if (!S.contains(num)) {
S.add(num);
}
break;
case "remove":
num = Integer.parseInt(st.nextToken());
S.remove((Integer)num);
break;
case "check":
num = Integer.parseInt(st.nextToken());
if (S.contains(num)) {
bw.write("1\n");
} else {
bw.write("0\n");
}
break;
case "toggle":
num = Integer.parseInt(st.nextToken());
if (S.contains(num)) {
S.remove((Integer)num);
} else {
S.add(num);
}
break;
case "all":
S.clear();
for (int x = 0; x <= 20; x++) {
S.add(x);
}
break;
case "empty":
S.clear();
break;
default:
break;
}
}
bw.close();
}
}
ㄴ ArrayList 를 이용해서 문제를 풀어도 정답을 맞출 수 있었다. 하지만 시간이 다소 걸리는 것을 확인했다.
두 번째 작성 코드
import java.io.*;
import java.util.*;
public class Main {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int M = Integer.parseInt(br.readLine());
int S = 0; // 비트마스크로 집합 표현, 1~20 비트 사용
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String input = st.nextToken();
int x = 0;
switch (input) {
case "add":
x = Integer.parseInt(st.nextToken());
S |= (1 << (x - 1)); // x에 해당하는 비트를 1로 설정
break;
case "remove":
x = Integer.parseInt(st.nextToken());
S &= ~(1 << (x - 1)); // x에 해당하는 비트를 0으로 설정
break;
case "check":
x = Integer.parseInt(st.nextToken());
int ret = (S & (1 << (x - 1))) == 0 ? 0 : 1; // x에 해당하는 비트 확인
bw.write(ret + "\n");
break;
case "toggle":
x = Integer.parseInt(st.nextToken());
S ^= (1 << (x - 1)); // x에 해당하는 비트를 반전
break;
case "all":
S = (1 << 20) - 1; // 모든 비트를 1로 설정
break;
case "empty":
S = 0; // 모든 비트를 0으로 설정
break;
}
}
br.close();
bw.flush();
bw.close();
}
}
ㄴ 비트마스크를 사용하여 집합을 효과적으로 표현하고 관리하도록 했다. 시간단축을 목표로 했지만 ArrayList를 사용했을 때와 시간이 비슷하게 걸렸다.
ㄴ 비트마스킹을 이용한 방법이 시간이 조금 더 걸렸다.
비트마스크
정수의 이진수 표현을 활용하여 집합의 원소 여부를 나타내는 방식이다.
코드에서 사용한 예시를 보면,
int S = 0;
ㄴ 비트마스크로 표현되는 집합을 나타내는 변수 S를 초기화합니다.
S |= (1 << (x - 1));
ㄴ add 연산에서는 x에 해당하는 비트를 1로 설정하여 집합에 원소를 추가한다. 여기서 1 << (x - 1)는 x에 해당하는 비트만 1로 설정된 정수를 나타냅니다. |=는 비트 OR 연산자로, 해당 비트를 집합에 추가합니다.
ㄴ 여기서 1 << (x - 1)는 왼쪽 시프트(Left Shift) 연산을 나타낸다. 이는 이진수 표현에서 비트를 왼쪽으로 이동시키는 연산이다.
ㄴ 1 << (x - 1)의 의미는 1을 이진수로 표현했을 때, 가장 오른쪽 비트를 왼쪽으로 (x - 1)만큼 이동시킨다는 것이다.
ㄴ 여기서 (x - 1)은 이동할 비트의 수(비트의 위치)를 나타낸다. 이진수에서 가장 오른쪽 비트의 위치를 1로 표현하고자 하는 것이다.ㄴ 이진수의 각 비트 위치는 0부터 시작하며, 왼쪽으로 이동할수록 해당 위치의 값은 2의 거듭제곱으로 증가한다.
ex) x가 3인 경우를 생각해보면, 1 << (3 - 1)은 1 << 2가 되고, 이는 2의 2승(4)가 된다.
ㄴ 이렇게 하면 해당 위치의 비트가 1이 되고, 나머지 비트는 0이 된다.
ex) 2비트만큼 왼쪽으로 이동하면 다음과 같이 된다. => 0001 (원래 1의 이진수 표현) -> 0100 (2비트 왼쪽으로 이동)
ㄴ 따라서 1 << (x - 1)을 사용하면, x 비트가 1이되고, 나머지 비트는 0인 이진수를 얻게되어 2^(x-1)과 같은 결과를 갖는다. 이는 주로 비트마스크 연산에서 특정 비트를 셋팅하기 위해 사용된다.
S &= ~(1 << (x - 1));
ㄴ remove 연산에서는 x에 해당하는 비트를 0으로 설정하여 집합에서 원소를 제거한다.
ㄴ ~(1 << (x - 1))는 x에 해당하는 비트만 0으로 설정된 정수를 나타낸다. &=는 비트 AND 연산자로, 해당 비트를 집합에서 제거한다.
ㄴ 자세히 말하자면, 여기서 1 << (x - 1)은 x 비트만 1이고 나머지 비트는 0인 이진수를 나타낸다. ~는 비트를 반전시키는 연산자이므로 ~(1 << (x - 1))은 x 비트만 0이고 나머지 비트는 1인 이진수를 얻게 된다.
ㄴ 그리고 S &= ~(1 << (x - 1));는 비트 AND 연산을 수행한다. 따라서 S의 x 비트가 1이면 0으로, 0이면 그대로 유지됩니다. 결과적으로 S에서 x 비트를 0으로 만들게 됩니다.
ㄴ 예를 들어, 현재 S의 상태를 이진수로 표현하면 {1, 2, 4}를 나타내는 이진수라고 하자. (이진수로는 0111)
ㄴ remove 2를 수행하면 원소 2의 비트를 0으로 만들어야 한다. 이때 1 << (2 - 1) 연산을 통해 2의 위치를 나타내는 비트를 찾고, 그 비트를 반전시켜 해당 위치의 값을 0으로 만든다.
ㄴ 1 << (2 - 1)은 1 << 1로, 이는 2의 이진수 표현에서 두 번째 비트를 나타내어 결과는 0010이다.
ㄴ ~ 연산자를 사용하여 비트를 반전시키면, 결과는 1101이다.
ㄴ S &= ~(1 << (2 - 1))을 수행하여 현재 S의 상태와 1101을 AND 연산하면, 해당 비트를 0으로 만든다.
ㄴ 결과적으로 S는 {1, 4}를 나타내는 이진수 0101이 된다.
ㄴ 이렇게 remove 2를 통해 2가 집합에서 제거된 것이다.
int ret = (S & (1 << (x - 1))) == 0 ? 0 : 1;
ㄴ check 연산에서는 x에 해당하는 비트를 확인하여 결과를 출력한다.
ㄴ (S & (1 << (x - 1)))는 x에 해당하는 비트가 0인지 1인지 확인하며, 삼항 연산자를 사용하여 결과를 결정한다.
ㄴ 1 << (x - 1)는 x를 이진수로 표현했을 때, x의 위치에 해당하는 비트를 1로 만들기 위한 연산이다.
ㄴ x가 1일 때는 1을 왼쪽으로 0번 시프트하므로 그대로 1이 되고, x가 2일 때는 1을 왼쪽으로 1번 시프트하므로 2의 이진수 위치에 해당하는 비트가 1이 된다.
ㄴ (S & (1 << (x - 1)))는 현재 집합 S와 위에서 계산한 값을 AND 연산하는 부분이다.
ㄴ 이것은 x의 위치에 해당하는 비트가 현재 S에서 1인지 0인지를 확인하는 역할을 한다.
ㄴ 만약 해당 비트가 1이면 결과는 0이 아니므로 (S & (1 << (x - 1)))의 값은 0이 아닌 어떤 값이 된다.
ㄴ 반대로, 해당 비트가 0이면 AND 연산 결과는 0이 된다.
ㄴ (S & (1 << (x - 1))) == 0 ? 0 : 1는 삼항 연산자를 사용하여 최종적으로 x의 위치에 해당하는 비트가 0이면 0을, 1이면 1을 결과로 반환한다. 즉, 해당 비트가 존재하면 1, 존재하지 않으면 0을 반환한다.
S ^= (1 << (x - 1));
ㄴ toggle 연산에서는 x에 해당하는 비트를 반전시켜 집합을 업데이트 한다.
ㄴ ^=는 비트 XOR 연산자로, 해당 비트를 반전시킨다.
ㄴ 1 << (x - 1)는 x에 해당하는 비트만 1로 된 값을 생성하기 위한 연산이다. x가 1이면 1을 왼쪽으로 0번 시프트하므로 1이 되고, x가 2일 때는 1을 왼쪽으로 1번 시프트하므로 2의 이진수 위치에 해당하는 비트가 1이 된다.
ㄴ S ^= (1 << (x - 1))는 XOR 연산을 사용하여 현재 S와 위에서 계산한 값을 XOR하는 부분이다. XOR 연산은 두 비트가 서로 다를 때 1을 반환하고, 같을 때 0을 반환한다. 따라서 해당 비트가 1이면 결과는 0이 되고, 해당 비트가 0이면 결과는 1이 됩니다. 즉, x의 상태를 뒤집는 효과가 있다.
S = (1 << 20) - 1;
ㄴ all 연산에서는 모든 비트를 1로 설정하여 집합을 초기화한다.
ㄴ 1 << 20는 2의 20승을 의미하며, 이는 이진수로 나타낼 때 20번째 비트가 1이고 나머지는 0인 값을 생성한다.
ㄴ (1 << 20) - 1처럼 2의 20승에서 1을 빼면, 이진수로 나타낼 때 20개의 비트가 모두 1인 값을 얻을 수 있다.
S = 0;
ㄴ empty 연산에서는 모든 비트를 0으로 설정하여 집합을 초기화한다.
ㄴ 0은 이진수로 나타낼 때 모든 비트가 0인 값을 의미한다. 따라서, S에는 0이 저장되고, 이는 공집합을 나타낸다.
문제점 : ArrayList로 문제를 풀어냈지만, 문제 알고리즘 분류가 비트마스킹으로 돼있어서 비트마스킹으로 풀어보려고 했다.
해결 방법 : 비트마스킹을 이용해 문제를 풀도록 했다.
비트마스킹을 이용해 코드를 작성하여 실행해봤지만, 실행시간은 비슷하게 걸려서 딱히 의미는 없었다.
깨달은 바 : 이번 기회에 비트마스킹에 대해 공부할 수 있었다.