[알고리즘] 집합 (백준 11723번)

11723번: 집합

 가장 기본적인 비트마스크 문제다. 총 M의 크기가 최대 3백만이고 메모리 허용량이 4MB 밖에 되지 않기에 비트마스크를 필히 활용해야 한다.

 

Solution

 비트마스크 연산 방법대로 분기해서 처리했는데도 시간초과가 나서 당황했는데 자바의 bufferedReader와 bufferedWriter를 써주지 않아서 그랬다.

 

 참고로 all 연산은 1~20까지의 수를 추가하는 것인데 이는

• (0~20) = SET의 21 추가후 - 1
• (1~20) = SET에서 - 1

이기에 최종적으로는 SET에 21을 추가후 -2 한 것과 같다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter


var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))


fun solution() {

    var M = readLine()!!.toInt()
    var set = 0

    for(i in 0 until M)
    {
        var list = br.readLine()!!.split(" ")
        var order = list[0]

        when(order)
        {
            "add" -> {
                var num = list[1].toInt()
                set = set or (1 shl num)
            }

            "remove" -> {
                var num = list[1].toInt()
                set = set and (1 shl num).inv()
            }

            "check" -> {
                var num = list[1].toInt()
                if(set and (1 shl num) > 0)
                    bw.write("1\n")
                else
                    bw.write("0\n")
            }

            "toggle" -> {
                var num = list[1].toInt()
                set = set xor (1 shl num)
            }

            "all" -> {
                set = (0 or (1 shl 21)) - 2
            }

            "empty" -> set = 0

        }

    }

}



fun main() {
    solution()
    br.close()
    bw.close()

}