[백준] 11723번 집합

백준 11723번 - 집합

문제

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

제약조건: M (1 ≤ M ≤ 3,000,000)

접근 방법

1~20까지만 존재하므로 20개의 비트 생성

생성 후 위의 연산에 맞는 비트 연산 실행

add

1로 만들기 위해 1과 or 연산

remove

제거하기 위해 1인 경우 1과 xor 연산

check

x에 위치하는 인덱스가 1인지 확인

toggle

1 -> 0
0 -> 1
을 만들 기 위해 xor 연산

all

모두 1로

empty

모두 0으로

코드

class IO11723 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun getM() = br.readLine().toInt()
    fun getOperation() = br.readLine().split(" ")
    fun flush() = bw.flush()
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    val io = IO11723()
    val m = io.getM()

    var bit: Long = 0b0 shl 19

    repeat(m) {
        val op = io.getOperation()
        val num = if (op.size == 2) op[1].toInt() else 0
        when (op[0]) {
            "add" -> {
                val comparison = 0b1 shl (num - 1)
                bit = bit or comparison.toLong()
            }
            "remove" -> {
                val str = bit.toString(2)
                if (str.length >= num && str[str.lastIndex - num + 1] == '1') {
                    val comparison = 0b1 shl (num - 1)
                    bit = bit xor comparison.toLong()
                }
            }
            "check" -> {
                val str = bit.toString(2)
                if (str.length >= num && str[str.lastIndex - num + 1] == '1') {
                    io.write("1\n")
                } else {
                    io.write("0\n")
                }
            }
            "toggle" -> {
                val comparison = 0b1 shl (num -1)
                bit = (bit xor comparison.toLong())
            }
            "all" -> {
                bit = 0b1
                repeat (19) {
                    bit = (bit shl 1) or 0b1
                }
            }
            "empty" -> {
                bit = 0b0 shl 19
            }
        }
    }

    io.flush()
    io.close()

}