[TIL, 일일 회고] 2024.11.20 - 비트마스크를 이용한 백준-집합 문제 풀이

 

개요

[Java] 비트 연산(bit)과 비트마스크(bit mask) 알아보기

 

위 포스팅에서 비트 마스크에 대해서 알아보았습니다. "백준. - 집합" 문제는 비트마스크를 활용하기에 적합한 문제입니다. 본 글에서는 비트 마스크의 특징과 이를 활용한 집합 연산 문제 해결 방법을 상세히 탐구하고자 합니다.

 

나의 풀이 및 설명

import java.io.*;
import java.util.*;

public class SetOperationsBitmask {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 초기 집합을 0으로 초기화
        int S = 0;
        
        // 연산 횟수 입력
        int M = Integer.parseInt(br.readLine());
        
        // 연산 수행
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String op = st.nextToken();
            
            switch (op) {
                case "add":
                    int x = Integer.parseInt(st.nextToken());
                    S |= (1 << (x - 1));  // x 추가
                    break;
                
                case "remove":
                    x = Integer.parseInt(st.nextToken());
                    S &= ~(1 << (x - 1));  // x 제거
                    break;
                
                case "check":
                    x = Integer.parseInt(st.nextToken());
                    bw.write(((S & (1 << (x - 1))) != 0 ? "1" : "0") + "\n");
                    break;
                
                case "toggle":
                    x = Integer.parseInt(st.nextToken());
                    S ^= (1 << (x - 1));  // x 토글
                    break;
                
                case "all":
                    S = (1 << 20) - 1;  // 1~20까지 모든 비트를 1로 설정
                    break;
                
                case "empty":
                    S = 0;  // 모든 비트를 0으로 초기화
                    break;
            }
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}

 

1. add x

S |= (1 << (x - 1))

 

• 1 << (x - 1)
  • x번째 비트를 1로 만드는 비트 마스크 생성
• |=
  • OR 연산으로 해당 비트를 집합에 추가
• 예: x = 3이면 0001 | 0100 = 0101 (두 비트 중 하나라도 1이면 1이 됨)

2. remove x

S &= ~(1 << (x - 1))

 

• 1 << (x - 1)
  • x번째 비트 위치 생성
• ~
  • NOT 연산으로 해당 비트를 0으로 만듦
• &=
  • AND 연산으로 해당 비트 제거
• 예: x = 3이면 1111 & 1011 = 1011 (두 비트가 모두 1인 자리만 1 유지)

 

3. check x

 

(S & (1 << (x - 1))) != 0

 

• 1 << (x - 1)
  • x번째 비트 위치 생성
• &
  • AND 연산으로 해당 비트 존재 확인
• 0이 아니면 1(존재), 0이면 0(미존재)

 

4. toggle x

S ^= (1 << (x - 1))

 

• 1 << (x - 1)
  • x번째 비트 위치 생성
• ^=
  • XOR 연산으로 비트 상태 반전
• 예: 0101 ^ 0100 = 0001 (두 비트가 다르면 1, 같으면 0)

 

5. all

S = (1 << 20) - 1

• 1 << 20
  • 20번째 비트를 1로 설정
• -1
  • 모든 하위 비트를 1로 만듦
• 결과: 1~20까지 모든 비트가 1

6. empty

S = 0

• 모든 비트를 0으로 초기화