[Java] baekjoon_11723 : 집합

구현, 비트마스킹

집합 : Silver5

https://www.acmicpc.net/problem/11723

11723번: 집합

 

첫 번째 작성 코드

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로 문제를 풀어냈지만, 문제 알고리즘 분류가 비트마스킹으로 돼있어서 비트마스킹으로 풀어보려고 했다.

해결 방법 : 비트마스킹을 이용해 문제를 풀도록 했다.

비트마스킹을 이용해 코드를 작성하여 실행해봤지만, 실행시간은 비슷하게 걸려서 딱히 의미는 없었다. 

깨달은 바 : 이번 기회에 비트마스킹에 대해 공부할 수 있었다.