[Algorithm/Kotlin] 백준 11723번 집합: 집합 연산 최적화 MutableSet vs. 비트마스크(Bitmask)

 

이번 글에서는 MutableSet과 비트마스크(Bitmask) 두 가지 방식을 비교하며, 새롭게 알게 된 비트마스크를 활용한 집합 연산 최적화 방법을 정리해보겠습니다.

---

1. 문제 설명

비어있는 공집합 S가 주어졌을 때, 다음 연산을 수행하는 프로그램을 작성하세요.

• add x : S에 x를 추가 (1 ≤ x ≤ 20)
• remove x : S에서 x를 제거
• check x : S에 x가 있으면 1, 없으면 0 출력
• toggle x : S에 x가 있으면 제거, 없으면 추가
• all : S를 {1, 2, ..., 20}으로 변경
• empty : S를 공집합 {}으로 변경

입력

• M (1 ≤ M ≤ 3,000,000): 연산 개수
• 이후 M개의 연산이 주어짐

출력

• check 연산이 수행될 때마다 결과를 출력

---

2. 문제 해결 아이디어

이 문제를 해결하는 방법은 크게 두 가지가 있습니다.

1. MutableSet<Int>를 사용하여 직접 집합을 관리하는 방식
2. 비트마스크(Bitmask)를 사용하여 Int 변수 하나로 집합을 관리하는 방식

각 방식의 장단점을 비교하면서 설명해보겠습니다.

---

3. 방법 1: MutableSet을 이용한 해결 방법

가장 직관적인 방식으로, MutableSet<Int>를 사용하여 1~20 범위의 숫자를 저장하고 관리합니다.

구현 코드

var s: MutableSet<Int> = mutableSetOf()

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    repeat(n) {
        val input = br.readLine().split(" ")
        when (input[0]) {
            "add" -> s.add(input[1].toInt())
            "remove" -> s.remove(input[1].toInt())
            "check" -> bw.write("${if (s.contains(input[1].toInt())) 1 else 0}\n")
            "toggle" -> if (s.contains(input[1].toInt())) s.remove(input[1].toInt()) else s.add(input[1].toInt())
            "all" -> s = (1..20).toMutableSet()
            "empty" -> s.clear()
        }
    }
    bw.flush()
    bw.close()
}

시간 복잡도 분석

• add(x), remove(x), check(x), toggle(x) → O(1) (Set의 기본 연산)
• all() → O(1) (Set을 새로 생성)
• empty() → O(1) (clear() 호출)
• 총 시간 복잡도: O(M)

---

4. 방법 2: 비트마스크를 활용한 해결 방법

비트마스크(Bitmask)란?

비트 연산을 활용하여 데이터를 효율적으로 표현하는 기법으로, 정수형 변수의 각 비트를 상태(flag)로 사용하여 특정 값을 저장하거나 조작할 수 있습니다.

이 문제에서는 정수형 변수(Int)의 하위 20비트를 활용하여 1~20까지의 숫자 집합을 표현합니다.

• 1: 해당 숫자가 포함됨
• 0: 해당 숫자가 포함되지 않음

비트 연산자 정리

연산자	의미	사용 예제
or (|)	해당 위치의 비트가 무조건 1로 변경됨, 기존 값이 1이면 유지, 0이면 1로 변경	특정 비트를 1로 설정 (값 추가)
and (&)	특정 비트가 1인지 확인	if (S and (1 shl (x - 1)) != 0)
xor (^)	특정 비트를 토글 (1 ↔ 0)	S = S xor (1 shl (x - 1))
inv (inv())	특정 비트를 0으로 변경 (값 제거)	S = S and (1 shl (x - 1)).inv()
shl(n)	비트를 n칸 왼쪽으로 이동	1 shl n

구현 코드

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    var S = 0 // 비트마스크로 사용할 정수

    val bw = System.out.bufferedWriter()

    repeat(n) {
        val str = readLine().split(" ")
        when (str[0]) {
            "add" -> S = S or (1 shl (str[1].toInt() - 1))
            "remove" -> S = S and (1 shl (str[1].toInt() - 1)).inv()
            "check" -> bw.write(if (S and (1 shl (str[1].toInt() - 1)) != 0) "1\n" else "0\n")
            "toggle" -> S = S xor (1 shl (str[1].toInt() - 1))
            "all" -> S = (1 shl 20) - 1
            "empty" -> S = 0
        }
    }
    bw.flush()
    bw.close()
}

 

비트 연산 방식 설명

연산	비트 연산 코드	설명
add x	S = S or (1 shl (x - 1))	x번째 비트를 1로 설정
remove x	S = S and (1 shl (x - 1)).inv()	x번째 비트를 0으로 설정
check x	if (S and (1 shl (x - 1)) != 0)	x번째 비트가 1인지 확인
toggle x	S = S xor (1 shl (x - 1))	x번째 비트를 반전 (토글)
all	S = (1 shl 20) - 1	1~20 모든 숫자 추가
empty	S = 0	공집합으로 초기화

시간 복잡도 분석

• 모든 연산이 O(1) (비트 연산은 상수 시간에 수행됨)
• 총 시간 복잡도: O(M)

---

5. 두 가지 방법 비교

방식MutableSet 사용비트마스크 사용

메모리 사용	높음 (Set 자료구조 필요)	낮음 (Int 변수 1개)
연산 속도	O(1) (빠름)	O(1) (더 빠름)
구현 난이도	쉬움	다소 어려움
확장성	1~20 범위를 넘어갈 수 있음	Int 크기(32비트)까지 제한

 

• 입력 크기가 작다면 MutableSet 방식이 직관적이고 편리
• 입력 크기가 크다면 비트마스크 방식이 더 빠르고 메모리 효율적

---

정리

• MutableSet 방식은 일반적인 Set 자료구조를 활용한 방식
• 비트마스크 방식은 비트 연산을 활용하여 Int 하나로 집합을 표현하는 방식
• 입력 크기가 클수록 비트마스크 방식이 더 효율적

---

문제링크: https://www.acmicpc.net/problem/11723